ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4749: 魔术粉

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：27 通过：16
提交提交记录统计Web Board

题目描述


  这个问题有两个版本，它们仅在约束上有所不同。如果可以在较大的约束中解决此问题，则可以为两个版本编写一个解决方案。如果在较大的约束中发现问题太难，则可以仅将解决方案写入简化版本。
  早晨醒来，阿波利纳利亚决定烤饼干。为了烤一块饼干，她需要n种原料，对于每一种原料，她知道其价值ai——烤一块饼干需要多少克这种原料。为了准备一块饼干，Apollinaria需要使用所有n种材料。
  阿波利纳里亚含有第i种成分bi克。她还有k克的魔法粉。每克神奇粉末可以正好变成 1 克 n 种成分中的任何一种，可用于烘焙饼干。
  你的任务是确定饼干的最大数量，阿波利纳里亚能够使用她拥有的成分和神奇的粉末烘烤这些饼干。

This problem is given in two versions that differ only by constraints. If you can solve this problem in large constraints, then you can just write a single solution to the both versions. If you find the problem too difficult in large constraints, you can write solution to the simplified version only.
Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value ai− how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.
Apollinaria has bi gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.
Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder.

Input
The first line of the input contains two positive integers n and k (1≤n,k≤1000)− the number of ingredients and the number of grams of the magic powder.
The second line contains the sequence a1,a2,...,an (1≤ai≤1000), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.
The third line contains the sequence b1,b2,...,bn (1≤bi≤1000), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.
Output
Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.
Examples
Input 
3 1
2 1 4
11 3 16
Output 
4
Input 
4 3
4 3 5 6
11 12 14 20
Output 
3
Note
In the first sample it is profitably for Apollinaria to make the existing 1 gram of her magic powder to ingredient with the index 2, then Apollinaria will be able to bake 4 cookies.
In the second sample Apollinaria should turn 1 gram of magic powder to ingredient with the index 1 and 1 gram of magic powder to ingredient with the index 3. Then Apollinaria will be able to bake 3 cookies. The remaining 1 gram of the magic powder can be left, because it can't be used to increase the answer.

输入格式

输入的第一行包含两个正整数 n 和 k （1≤n，k≤1000）− 原料的数量和魔法粉末的克数。
第二行包含序列 a1，a2,...,an （1≤ai≤1000），其中第 i 个数字等于烘烤一块饼干所需的第 i 种原料的克数。
第三行包含序列 b1，b2,...,bn （1≤bi≤1000），其中第 i 个数字等于第 i 个原料的克数，Apollinaria 具有的。

输出格式

打印最大数量的饼干，Apollinaria 将使用她拥有的原料和神奇的粉末烘烤这些饼干。

输入样例 复制 

3 1
2 1 4
11 3 16

输出样例 复制 

4

数据范围与提示

注意
在第一个样品中，Apollinaria 将现有的 1 克她的神奇粉末制成种类为 2 的成分是有利可图的，那么 Apollinaria 将能够烘烤 4 块饼干。
在第二个样品中，Apollinaria应将1克魔粉转换为种类为1的成分，1克魔粉转换为种类为3的成分。然后Apollinaria将能够烤3个饼干。剩下的那1克魔粉可以留下，因为它不能用来增加答案。

分类标签