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, $\frac{\sum_{j = 1}^{m} a_{j}}{\sum_{j = 1}^{m} b_{j}} = k$ , where a_{j} is the taste of the j-th chosen fruit and b_{j} 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 a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100) — the fruits' tastes. The third line of the input contains n integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 100) — the fruits' calories. Fruit number i has taste a_{i} and calories b_{i}.


-----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 $\frac{18}{9} = 2 = k$ fulfills, that's exactly what Inna wants.

In the second test sample we cannot choose the fruits so as to follow Inna's principle.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(n, k) = [int(x) for x in input().split(' ')]
taste = [int(x) for x in input().split(' ')]
cal = [int(x) for x in input().split(' ')]
w = [taste[i] - k * cal[i] for i in range(n)]
taste_per_diff = [-1 for i in range(50000)]
shift = 20000
taste_per_diff[shift] = 0
for i in range(n):
	new_tpd = [x for x in taste_per_diff]
	for j in range(0, 40000):
		if taste_per_diff[j] != -1:
			new_tpd[j + w[i]] = max(new_tpd[j + w[i]], taste_per_diff[j] + taste[i])
	taste_per_diff = new_tpd
if taste_per_diff[shift] == 0:
	print(-1)
else:
	print(taste_per_diff[shift])


class Dict(dict):

	def __missing__(self, key):
		return float('-inf')
(n, k) = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
dp = [Dict() for _ in range(n + 1)]
dp[0][n * 100] = 0
for i in range(1, n + 1):
	s = a[i] - b[i] * k
	for j in range(n * 200, s - 1, -1):
		dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - s] + a[i])
print(dp[n][n * 100] or -1)


from sys import stdin, stdout
Pi = lambda x: stdout.write(str(x) + '\n')
Ps = lambda x: stdout.write(str(x))
S = lambda x: x * (x + 1) // 2
I = lambda x: 1 + 2 * x
R = lambda : stdin.readline()
Ri = lambda x: list(map(int, x.split()))
Rs = lambda x: list(map(str, x.split()))
Rf = lambda x: list(map(float, x.split()))
MaxN = int(100000.0) + 10

def f(i, x, n, k, dp, A, B):
	if i == n:
		if x == 0:
			return 0
		return -1000000
	if dp[i][x + MaxN] != -1:
		return dp[i][x + MaxN]
	op1 = f(i + 1, x + A[i] - B[i] * k, n, k, dp, A, B) + A[i]
	op2 = f(i + 1, x, n, k, dp, A, B)
	dp[i][x + MaxN] = max(op2, op1)
	return dp[i][x + MaxN]

def main():
	for x in stdin:
		(n, x) = Ri(x)
		A = list(Ri(R()))
		B = list(Ri(R()))
		dp = []
		for i in range(110):
			dp.append([-1] * (MaxN * 2))
		ans = f(0, 0, n, x, dp, A, B)
		if ans < 1:
			ans = -1
		Pi(ans)

def __starting_point():
	main()
__starting_point()


[n, k] = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
b.insert(0, 0)
a.insert(0, 0)
s = sum(b) * k
f = [[0 for i in range(0, 4 * s + 1)] for j in range(0, n + 1)]
for i in range(0, n + 1):
	a[i] = a[i] - k * b[i]
for i in range(1, n + 1):
	for j in range(s, 3 * s + 1):
		f[i][j] = f[i - 1][j]
		if j - a[i] == 2 * s or f[i - 1][j - a[i]] > 0:
			f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + b[i])
if f[n][2 * s]:
	print(f[n][2 * s] * k)
else:
	print(-1)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list([int(x) * k for x in input().split()])
pos = [0] * 10 ** 5
neg = [0] * 10 ** 5
pos[0] = 1
neg[0] = 1
base = 0
for i in range(n):
	d = a[i] - b[i]
	if d > 0:
		for j in range(10 ** 5 - 1, -1, -1):
			if pos[j]:
				if j + d < 10 ** 5:
					pos[j + d] = max(pos[j + d], pos[j] + a[i])
	elif d < 0:
		for j in range(10 ** 5 - 1, -1, -1):
			if neg[j]:
				if j - d < 10 ** 5:
					neg[j - d] = max(neg[j - d], neg[j] + a[i])
	else:
		base += a[i]
best = 0
for i in range(10 ** 5):
	if pos[i] and neg[i]:
		best = max(best, pos[i] + neg[i])
best -= 2
best += base
if best:
	print(best)
else:
	print(-1)


k = int(input().split()[1])
a = [int(s) for s in input().split()]
b = [int(s) for s in input().split()]
ambk = [(a[i], a[i] - b[i] * k) for i in range(len(a))]
ambk.sort(key=lambda a: -a[1])
ts = [0] * (100 * 100)
keys = [0]
atras = list(range(100 * 100 - 1, -1, -1))
adelante = list(range(100 * 100))
for i in range(len(a)):
	for j in atras if ambk[i][1] >= 0 else adelante:
		if ts[j] > 0 or j == 0:
			if j + ambk[i][1] >= 0:
				ts[j + ambk[i][1]] = max(ts[j + ambk[i][1]], ts[j] + ambk[i][0])
print('-1' if ts[0] == 0 else str(ts[0]))


(n, k) = list(map(int, input().split()))
s = list(map(int, input().split()))
s1 = list(map(int, input().split()))
dp = [[[0 for j in range(10 ** 5)] for l in range(2)] for i in range(n + 1)]
y = s[0] - s1[0] * k
if y >= 0:
	dp[0][0][y] = s[0]
else:
	dp[0][1][-y] = s[0]
for i in range(1, n):
	y = s[i] - s1[i] * k
	for j in range(100 ** 2 + 2):
		for l in range(2):
			dp[i][l][j] = max(dp[i][l][j], dp[i - 1][l][j])
			if dp[i - 1][l][j] != 0 or j == 0:
				if l == 1:
					x = -j + y
				else:
					x = j + y
				if x < 0:
					x = abs(x)
					dp[i][1][x] = max(dp[i - 1][1][x], dp[i][1][x], dp[i - 1][l][j] + s[i])
				else:
					dp[i][0][x] = max(dp[i - 1][0][x], dp[i][0][x], dp[i - 1][l][j] + s[i])
if dp[n - 1][0][0] == 0:
	print(-1)
else:
	print(dp[n - 1][0][0])


(n, k) = map(int, input().split())
(x, y) = ([0] * 100001, [0] * 100001)
x[0] = y[0] = 1
g = h = 0
for (u, v) in zip(*(map(int, input().split()), map(int, input().split()))):
	d = u - k * v
	if d > 0:
		for j in range(g, -1, -1):
			if x[j]:
				x[j + d] = max(x[j + d], x[j] + v)
		g += d
	else:
		for j in range(h, -1, -1):
			if y[j]:
				y[j - d] = max(y[j - d], y[j] + v)
		h -= d
s = max((x[i] + y[i] for i in range(min(g, h) + 1) if x[i] and y[i])) - 2
print(k * s - (not s))


from collections import defaultdict
(n, k) = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))
dp = [defaultdict(lambda : int(-2000000000.0)) for _ in range(n + 1)]
dp[0][n * 100] = 0
for i in range(1, n + 1):
	s = a[i] - b[i] * k
	for j in range(n * 200, -1, -1):
		dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - s] + a[i])
print(dp[n][n * 100] if dp[n][n * 100] > 0 else -1)


(n, k) = map(int, input().split())
a = [int(temp) for temp in input().split()]
b = [int(temp) for temp in input().split()]
c = [-a[i] + k * b[i] for i in range(n)]
lis = {0: 0}
lis1 = {0: 0}
for i in range(n):
	temp = lis.copy()
	for j in list(lis.keys()):
		if c[i] < 0:
			if j - c[i] in lis:
				lis[j - c[i]] = max(temp[j - c[i]], temp[j] + a[i])
			else:
				lis[j - c[i]] = temp[j] + a[i]
temp = list(lis)
temp.sort()
temp.reverse()
maxnum = temp[0]
for i in range(n):
	temp1 = lis1.copy()
	for j in list(lis1.keys()):
		if c[i] >= 0:
			if j + c[i] in lis1:
				lis1[j + c[i]] = max(temp1[j + c[i]], temp1[j] + a[i])
			elif j + c[i] <= maxnum:
				lis1[j + c[i]] = temp1[j] + a[i]
maxnum = 0
for i in temp:
	if i in lis1:
		maxnum = max(lis[i] + lis1[i], maxnum)
if maxnum == 0:
	print(-1)
else:
	print(maxnum)


(n, k) = [int(x) for x in input().split(' ')]
taste = [int(x) for x in input().split(' ')]
cal = [int(x) for x in input().split(' ')]
d = [[0 for j in range(10000 * 2)] for i in range(n)]
a = taste
b = cal
w = [a[i] - k * b[i] for i in range(n)]
dp = [-9999999 for i in range(300005)]
dp[10000] = 0
for i in range(n):
	if w[i] > 0:
		for j in range(20000, w[i], -1):
			if dp[j - w[i]] != -9999999:
				dp[j] = max(dp[j], dp[j - w[i]] + a[i])
	else:
		for j in range(20000):
			if dp[j - w[i]] != -9999999:
				dp[j] = max(dp[j], dp[j - w[i]] + a[i])
if dp[10000] == 0:
	print(-1)
else:
	print(dp[10000])


from bisect import bisect_right
(n, k) = map(int, input().split())
t = sorted(((u - k * v, v) for (u, v) in zip(*(map(int, input().split()), map(int, input().split())))))
m = n - bisect_right(t, (0, 0))
(l, p, t) = (0, [0] * 100001, t[::-1])
for (d, v) in t[:m]:
	for j in range(l, 0, -1):
		if p[j]:
			p[j + d] = max(p[j + d], p[j] + v)
	p[d] = max(p[d], p[0] + v)
	l += d
for (d, v) in t[m:]:
	for j in range(-d, l + 1):
		if p[j]:
			p[j + d] = max(p[j + d], p[j] + v)
print(p[0] * k if p[0] else -1)


(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
diff = []
for x in range(n):
	diff.append(a[x] - b[x] * k)
totals = {0: 0}
for x in range(n):
	t = a[x]
	d = diff[x]
	newGuys = []
	for y in totals:
		newGuys.append((y + d, totals[y] + t))
	for (y, z) in newGuys:
		if y in totals:
			totals[y] = max(totals[y], z)
		else:
			totals[y] = z
if totals[0] == 0:
	print(-1)
else:
	print(totals[0])
	if totals[0] == 1435:
		print(' '.join([str(x) for x in diff]))