#P1798. 小明搬家

小明搬家

题目描述

小明要搬家了,大家都来帮忙。

小明现在住在第 NN 楼,总共 KK 个人要把 XX 个大箱子搬上 NN 楼。

最开始 XX 个箱子都在 11 楼,但是经过一段混乱的搬运已经乱掉了。最后大家发现这样混乱地搬运过程效率太低了,于是总结出了提高效率的方法。

大家的速度都是每分钟上(或下)一层楼。所有向上走的人手中都拿一个箱子,所有向下走的人手中都不拿箱子。到达第 NN 层立刻放下箱子向下走,到达第 11 层立刻拿起箱子向上走。当一个人向上走,另一人向下走而在楼道里相遇时,向上走的人将手中的箱子交给另一人,两人同时反向。即原来拿箱子向上走的人不拿箱子向下走,原来不拿箱子向下走的人现拿着箱子向上走。

求将所有箱子搬完所需的最短时间。

输入格式

第一行 N,K,MN, K, M,分别表示楼层数、人数、还放在一楼地上的箱子数。

接下来 KK 行,每行两个数 Ai,BiA_i,B_i

AiA_i 表示第 ii 人现所在的楼层数,BiB_i0011,为 00 表示第 ii 人正拿着箱子向上走,为 11 表示第 ii 人不拿箱子向下走。

输入满足没有任意两人正在同一楼层,在第 11 层的人一定正拿着箱子向上走,在第 NN 层的人一定正不拿箱子向下走。

输出格式

仅包含一个整数,为搬完箱子的时间。

5 2 4
1 0
3 0

20

提示

对于 30%30\% 的数据,K100K \leq 100M100M \leq 100

对于 60%60\% 的数据,K1000K \leq 1000M109M \leq 10^9;

对于 100%100\% 的数据,N109N \le 10^9K5×105K \le 5 \times 10^5M109M \le 10^9