5885: 迪马和沙拉
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：4
通过：2
题目描述
迪玛、茵娜和谢廖扎聚集在一个房间里。没错，总得有人去。为了让谢廖扎振作起来，激励他散步，茵娜决定做点什么。
迪马和谢廖扎冰箱里有n个水果。每种水果都有两个参数：味道和卡路里的数量。茵娜决定做水果沙拉，所以她想从冰箱里拿出一些水果。茵娜在选择水果时遵循一定的原则：所选水果的总味道与总卡路里之比必须等于k。换句话说，其中aj是j选择的水果的味道，bj是它的卡路里。
茵娜还没有选择水果，她在想：如果严格遵循自己的原则，所选水果的最大味道是多少？帮助茵娜解决这个烹饪问题——现在一对年轻夫妇的幸福掌握在你手中！
茵娜非常喜欢迪玛，所以她想用至少一种水果做沙拉。
迪马和谢廖扎冰箱里有n个水果。每种水果都有两个参数：味道和卡路里的数量。茵娜决定做水果沙拉，所以她想从冰箱里拿出一些水果。茵娜在选择水果时遵循一定的原则：所选水果的总味道与总卡路里之比必须等于k。换句话说，其中aj是j选择的水果的味道，bj是它的卡路里。
茵娜还没有选择水果，她在想：如果严格遵循自己的原则，所选水果的最大味道是多少？帮助茵娜解决这个烹饪问题——现在一对年轻夫妇的幸福掌握在你手中！
茵娜非常喜欢迪玛，所以她想用至少一种水果做沙拉。
Dima, Inna and Seryozha have gathered in a room. That's right, someone's got to go. To cheer Seryozha up and inspire him to have a walk, Inna decided to cook something.
Dima and Seryozha have n fruits in the fridge. Each fruit has two parameters: the taste and the number of calories. Inna decided to make a fruit salad, so she wants to take some fruits from the fridge for it. Inna follows a certain principle as she chooses the fruits: the total taste to the total calories ratio of the chosen fruits must equal k. In other words, where aj is the taste of the j-th chosen fruit and bj is its calories.
Inna hasn't chosen the fruits yet, she is thinking: what is the maximum taste of the chosen fruits if she strictly follows her principle? Help Inna solve this culinary problem − now the happiness of a young couple is in your hands!
Inna loves Dima very much so she wants to make the salad from at least one fruit.
Dima and Seryozha have n fruits in the fridge. Each fruit has two parameters: the taste and the number of calories. Inna decided to make a fruit salad, so she wants to take some fruits from the fridge for it. Inna follows a certain principle as she chooses the fruits: the total taste to the total calories ratio of the chosen fruits must equal k. In other words, where aj is the taste of the j-th chosen fruit and bj is its calories.
Inna hasn't chosen the fruits yet, she is thinking: what is the maximum taste of the chosen fruits if she strictly follows her principle? Help Inna solve this culinary problem − now the happiness of a young couple is in your hands!
Inna loves Dima very much so she wants to make the salad from at least one fruit.
Input
The first line of the input contains two integers n, k (1≤n≤100,1≤k≤10). The second line of the input contains n integers a1,a2,...,an (1≤ai≤100) − the fruits' tastes. The third line of the input contains n integers b1,b2,...,bn (1≤bi≤100) − the fruits' calories. Fruit number i has taste ai and calories bi.
Output
If there is no way Inna can choose the fruits for the salad, print in the single line number -1. Otherwise, print a single integer − the maximum possible sum of the taste values of the chosen fruits.
Examples
Input
3 2 10 8 1 2 7 1
Output
18
Input
5 3 4 4 4 4 4 2 2 2 2 2
Output
-1
Note
In the first test sample we can get the total taste of the fruits equal to 18 if we choose fruit number 1 and fruit number 2, then the total calories will equal 9. The condition 
fulfills, that's exactly what Inna wants. In the second test sample we cannot choose the fruits so as to follow Inna's principle.
输入格式
输入的第一行包含两个整数 n， k （1≤n≤100，1≤k≤10）。输入的第二行包含 n 个整数 a1，a2,...,an （1≤ai≤100） - 水果的味道。输入的第三行包含 n 个整数 b1，b2,...,bn （1≤bi≤100） - 水果的卡路里。水果数 i 有味道 ai 和卡路里 bi。
输出格式
如果茵娜无法选择沙拉的水果，请打印单行编号 -1。否则，打印单个整数 - 所选水果的味道值的最大可能总和。
例子
输入
3 2
10 8 1
2 7 1
输出
18
输入
1 ·
4 4 4 4 4
2 2 2 2 2
输出
-1
注意
在第一个测试样本中，如果我们选择水果 1 和水果 2，我们可以得到等于 18 的水果总味道，那么总卡路里将等于 9。条件满足，这正是茵娜想要的。
在第二个测试样本中，我们不能选择水果以遵循茵娜的原则。
例子
输入
3 2
10 8 1
2 7 1
输出
18
输入
1 ·
4 4 4 4 4
2 2 2 2 2
输出
-1
注意
在第一个测试样本中，如果我们选择水果 1 和水果 2，我们可以得到等于 18 的水果总味道，那么总卡路里将等于 9。条件满足，这正是茵娜想要的。
在第二个测试样本中，我们不能选择水果以遵循茵娜的原则。
输入样例 复制
3 2
10 8 1
2 7 1输出样例 复制
18