← 返回题目列表

Codeforces · 366/C

C. 迪玛和沙拉

中文机器翻译题面 查看原题

Dima、Inna 和 Seryozha 聚集在一个房间里。没错,有人该走了。为了让 Seryozha 高兴起来并鼓励他去散步,Inna 决定做点东西。

Dima 和 Seryozha 冰箱里有 n 个水果。每种水果都有两个参数:味道和卡路里数。伊娜决定做一份水果沙拉,所以她想从冰箱里拿一些水果来做。 Inna 在选择水果时遵循一定的原则:所选水果的总味道与总热量的比率必须等于 k。换句话说, $$\frac{\sum_{j=1}^{m}a_j}{\sum_{j=1}^{m}b_j}=k$$ ,其中 aj 是第 j 个所选水果的味道,bj 是其卡路里。

Inna还没有选择水果,她在想:如果严格按照自己的原则,所选择的水果的最大味道是多少?帮助 Inna 解决这个烹饪问题——现在一对年轻夫妇的幸福就掌握在你的手中了!

Inna 非常喜欢 Dima,所以她想用至少一种水果制作沙拉。

输入

输入的第一行包含两个整数 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。

输出

如果 Inna 无法选择沙拉的水果,请在单行中打印数字 -1。否则,打印一个整数——所选水果的味道值的最大可能总和。

示例

输入 #1

3 2
10 8 1
2 7 1

输出 #1

18

输入 #2

5 3
4 4 4 4 4
2 2 2 2 2

输出 #2

-1

注意

在第一个测试样本中,如果我们选择水果号 1 和水果号 2,我们可以得到水果的总口味等于 18,那么总热量等于 9。条件 $$\frac{18}{9}=2=k$$ 满足,这正是 Inna 想要的。

在第二个测试样本中,我们不能选择水果,以遵循 Inna 原则。