You are given $n$ objects, a knapsack of capacity $c$, array $v$, and array $w$. The $i^{th}$ object has value v[i] and weight w[i].

Determine the maximum total value that you can get by selecting objects in such a manner that their sum of weights is not greater than the capacity $c$.

Input format

• First line: Two integers $n$ and $c$ denoting the number of objects and capacity of the knapsack ($1 \le n \le 10^3$ and $0 \le c \le 2×10^6$) 
• Second line: $n$ integers $v_1,\ v_2,\ ..., v_n$ ($0 \le v_i \le 50$)
• Third line: $n$ integers $w_1,\ w_2,\ ...,\ w_n$ ($0 \le w_i \le 2×10^6$)

Output format

Print a single integer denoting the maximum value that you can get by selecting the objects.