#A0020. 给军训收集阳光吧

给军训收集阳光吧

一年一度的军训又要到了,为了给马上要军训的同学们完整,良好的体验,我们来给他们收集阳光吧! (你想想看万一下雨了又热又湿多难受啊,你再想想下完雨地上全湿的坐上去多难受啊,你再再想想下雨了你要冒雨去上课,你再再再想想万一上课上一半下雨了又要冒雨回宿舍或者去食堂,所以让我们来集阳光吧)

Format

现在你要在一条路(L米)上每一米上放一个向日葵,最开始你有p朵向日葵,你每前进1m,你就需要放一朵向日葵,如果在中途中向日葵全部用完,那么你的任务就算失败,在图中共有n个花店,第i个花店在距离起点AiA_i米的位置,最多可以买BiB_i朵花,假设你的背包可以放无限朵向日葵,问你是否能够走到L处,如果可以请输出最少的购买次数(在一个花店中,无论买多少朵都算购买一次)否则输出-1

限制条件

  • 1≤N≤100001 \le N \le 10000
  • 1≤L≤1000000, 1≤P≤10000001 \le L \le 1000000,\ 1 \le P \le 1000000
  • 1≤Ai<L, 1≤Bi≤1001 \le A_i < L,\ 1 \le B_i \le 100

Input

第一行 N(花店数量),L,P(初始有多少向日葵) 第二行 N个数,A1A_1到AnA_n 第三行 N个数,B1B_1到BnB_n.

Output

−1-1或最少购买次数

Samples

4 25 10
10 14 20 21
10 5 2 4
2

Limitation

1s, 1024KiB for each test case.

你可能可以用下面知识

例子

priority_queue<int> q;
q.push(3);
q.push(1);
q.push(5);
cout << q.top(); //输出5,和插入顺序无关
return 0;