[问题描述]

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

小明现住在第N楼，总K个人要把X个大箱子搬上N楼。

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

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

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

[输入格式]

第一行N（N<=10^9）,K(k<=500000),M(m<=10^9),分别表楼层数，人数，还有放在一楼地上的箱子数。

接下来K行，每行两个数Ai，Bi。

Ai表示第i人现所在的楼层数，Bi为0或1，为0表法第i人正拿着箱子向上走，为1表示第i人不拿箱子向下走。

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

[输出格式]

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

[输入样例]

5 2 4
1 0
3 0

[输出样例]

20

[数据范围]

对于30%的数据有k<=100，M<=100

对于60%的数据有k<=1000，M<=10^9

对于100%的数据有k<=500000，M<=10^9