题目描述
植物大战僵尸这款游戏中，还有一个特别的玩法；玩家操纵僵尸进攻植物。
首先，僵尸有m种（每种僵尸都是无限多的），玩家可以选择何时的僵尸来进攻。使用第i种僵尸需要花费wi资源，可以得到pi的攻击效果。在这里，我们认为多个僵尸总的进攻效果就是他们每个攻击效果的代数和。地图共有n行，对于第i行，最左端有若干植物，这些植物需要至少qi的攻击才能被全部消灭。若一行上的植物全部被消灭，我们看成这一行被攻破。由于资源紧张，你只有总量为k 的资源，不一定能够攻破所有行。但僵尸博士希望攻破相邻的t行，并希望t尽量的大。你能帮他算出t的值吗？
3 11 39
5 2 11
3 1 7
5 3 6 10 3 2 4 200 1 1 1
4
样例说明：打掉 10 3 2 4 这相邻的4行，需要的最小代价是16+5+4+7=32，不超过39
数据规模
对于70%的数据： n<=1000；
对于100%的数据： n<=200000，m<=100，k<=1000，所有pi ,qi<=100000000
内存 128m 时限 2s
(lzg PS:pi,qi固然大,可k是小于1000的啊!)