599. Dima and Salad

0

Medium

Dima, Inna, and Seryozha are gathered in a room and need to decide who will leave. In order to motivate Seryozha to go for a walk, Inna plans to prepare a meal.
Dima and Seryozha have a total of n fruits in the fridge. Each fruit has two attributes: taste and calorie count. Inna wants to make a fruit salad and needs to select some fruits from the fridge. She follows a specific principle when choosing the fruits: the ratio of the total taste to the total calories of the selected fruits must be equal to k. In other words, where aj represents the taste of the j-th chosen fruit and bj represents its calorie count.
Inna has not yet chosen the fruits and is contemplating what the maximum taste of the selected fruits would be if she strictly adheres to her principle. Help Inna solve this culinary problem and determine the happiness of the young couple!
Inna loves Dima very much and wants to include at least one fruit in the salad.

Input Format

The first line of the input consists of two integers n and k. The second line of the input contains n integers a1, a2, ..., an representing the tastes of the fruits. The third line of the input contains n integers b1, b2, ..., bn representing the calorie counts of the fruits. Fruit number i has a taste of ai and a calorie count of bi.

Output Format

If there is no way for Inna to select fruits for the salad, output -1. Otherwise, output a single integer representing the maximum possible sum of the taste values of the selected fruits.

Example

Input

3 2
10 8 1
2 7 1

Output

18

Constraints

1 ≤ n ≤ 100, 1 ≤ k ≤ 10

1 ≤ ai ≤ 100

1 ≤ bi ≤ 100

1 ≤ ai ≤ 100

1 ≤ bi ≤ 100

Loading...

View Submissions

Console