这个问题有两个版本,仅区别在于约束。如果您可以在大约束下解决这个问题,那么您可以为这两个版本编写一个解决方案。如果您发现问题在大约束下太困难,您可以只编写简化版本的解决方案。
早上醒来,Apollinaria 决定烤饼干。为了烘烤一块饼干,她需要 n 种成分,并且对于每种成分,她都知道其值 ai——烘烤一块饼干需要多少克这种成分。要准备一块饼干 Apollinaria 需要使用所有 n 种成分。
Apollinaria 具有二克的第 i 种成分。她还有k克魔法粉。每克魔法粉可以恰好变成 1 克 n 种原料中的任意一种,可以用来烘烤饼干。
你的任务是确定 Apollinaria 使用她拥有的原料和魔法粉能够烘烤的饼干的最大数量。
输入
输入的第一行包含两个正整数n和k(1≤n,k≤1000)——魔粉的成分数量和克数。
第二行包含序列 a1, a2, ..., an (1 ≤ ai ≤ 1000),其中第 i 个数字等于烘焙一块饼干所需的第 i 个成分的克数。
第三行包含序列 b1, b2, ..., bn (1 ≤ bi ≤ 1000),其中第 i 个数字等于 Apollinaria 拥有的第 i 个成分的克数。
输出
打印阿波利纳里亚使用她拥有的原料和魔法粉能够烘烤的饼干的最大数量。
示例
输入 #1
3 1 2 1 4 11 3 16
输出 #1
4
输入 #2
4 3 4 3 5 6 11 12 14 20
输出 #2
3
注意
在第一个样本中,Apollinaria 将现有的 1 克魔法粉与索引 2 进行配料是有利可图的,然后 Apollinaria 将能够烘烤 4 个饼干。
在第二个样本中,Apollinaria 应该将 1 克魔法粉变成索引 1 的配料,再将 1 克魔法粉变成索引 3 的配料。然后 Apollinaria 将能够烘烤 3 个饼干。剩下的1克魔粉可以留下,因为它不能用来增加答案。