#6249. 「CodePlus 2017 11 月赛」汀博尔

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

nn 棵树,初始时每棵树的高度为 HiH_i,第 ii 棵树每月都会长高 AiA_i。现在有个木料长度总量为 SS 的订单,客户要求每块木料的长度不能小于 LL,而且木料必须是整棵树(即不能为树的一部分)。现在问你最少需要等多少个月才能满足订单。

输入格式

第一行 33 个用空格隔开的非负整数 n,S,Ln,S,L,表示树的数量、订单总量和单块木料长度限制。

第二行 nn 个用空格隔开的非负整数,依次为 H1,H2,,HnH_1,H_2,\dots ,H_n

第三行 nn 个用空格隔开的非负整数,依次为 A1,A2,,AnA_1,A_2,\dots ,A_n

输出格式

输出一行一个整数表示答案。

样例

样例输入

3 74 51
2 5 2
2 7 9

样例输出

7

样例解释

对于样例,在六个月后,各棵树的高度分别为 14,47,5614,47,56,此时无法完成订单。

在七个月后,各棵树的高度分别为 16,54,6516,54,65,此时可以砍下第 22 和第 33 棵树完成订单了。

数据范围与提示

测试点编号 nn 特殊约定
1 n=1n = 1 1SHi100001 \leq S \leq H_i \leq 10000
2 1S,L,Hi,Ai100001 \leq S, L, H_i, A_i \leq 10000
3 1n10001 \leq n \leq 1000
4
5
6 1S,L,Hi,Ai1091 \leq S, L, H_i, A_i \leq 10^9
7
8
9 1n200001 \leq n \leq 20000
10
11 1S,L10181 \leq S, L \leq 10^{18}1Hi,Ai1091 \leq H_i, A_i \leq 10^9
12
13 1n2000001 \leq n \leq 200000 L=1L = 1
14 SLS \leq L
15 1S,L10181 \leq S, L \leq 10^{18}1Hi,Ai1091 \leq H_i, A_i \leq 10^9
16
17
18
19
20

来自 CodePlus 2017 11 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/郑林楷 命题/郑林楷 验题/王聿中
Git Repo:https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。