Problem E: 运输货物

Problem E: 运输货物

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 32  Solved: 6
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI的仓库里有n个货物需要按顺序送到其他地点,并且他的货车有着容量限制k和重量限制w。
这意味着货车内装的箱子数量不能超过k并且总重量不能超过w。
将货车内的货物按顺序送完后,他需要回到仓库继续装货,直到所有货物均送达指定地点。
从仓库到一个地点,在两个不同地点之间转移,以及回到仓库都算一趟行程,请问PIPI送完货物需要的最少行程数是多少。

Input

多组输入。
第一行输入货物数n,地点数m,容量限制k,重量限制w(1<=n,m,k,w<=100000)。
接下来输入n行。
每行输入两个整数a,b,代表第i个货物需要送往的地点以及重量(1<=a<=m,1<=b<=w)。

Output

对于每组输入,输出PIPI送完所有货物需要的行程数。

Sample Input

4 3 3 6
1 2
3 3
3 1
3 2

Sample Output

4