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: interview

Starter code:

Solutions:
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 = 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 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()]
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()))
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 = [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])




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])




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(1e5) + 10
# dp,A = []
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():	
	# t = int(R())
	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()

# 60 == 360

__starting_point()

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(1e5) + 10
# dp,A = []
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():	
	# t = int(R())
	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()

# 60 == 360


__starting_point()

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)


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]))


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, -1, -1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-s] + a[i])

print(dp[n][n*100] or -1)


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)