Greedy Knapsack

Budi stumbled upon the classical 0-1 Knapsack Problem that he learned in his university class. There are $N$ items numbered from 1 to $N$. Item $i$ has a positive weight $W_i$ and a positive value $V_i$. The goal is to take zero or more items so that their total weight does not exceed $M$ and their total value is as large as possible.

Budi has not worked on this problem in a while and cannot remember how to solve it. So he devised a greedy algorithm. The algorithm processes the items one by one, from item 1 to item $N$. If item $i$ can be taken without the total weight exceeding $M$, it takes the item. Otherwise, it skips the item. The output is the total value of all taken items.

GreedyKnapsack(W[1..N], V[1..N], M):
   total_value = 0
   total_weight = 0
   for i = 1 to N:
      if total_weight + W[i] ≤ M:
         total_weight = total_weight + W[i]
         total_value = total_value + V[i]
   return total_value

Budi knows this greedy algorithm may not find the optimal solution, but he does not mind for now. He noticed that the output depends on $M$. So he runs the greedy algorithm for every $M$ from 1 to a given upper limit $T$, and wants to find the largest output he can get.

For example, let $N = 5$, $T = 10$, $W_{1..5} = \{10, 1, 2, 3, 4\}$, and $V_{1..5} = \{1, 1, 1, 1, 1\}$. The largest output is 3, for instance with $M = 6$. The greedy algorithm takes items 2, 3, and 4, with a total weight of $1 + 2 + 3 = 6$ and a total value of $1 + 1 + 1 = 3$. If $M = 10$, the algorithm takes only item 1, with a total weight of 10 and a total value of 1.

Your task is to find the largest output the greedy algorithm can produce when $M$ ranges from 1 to $T$.

The first line contains two integers $N$ and $T$ ($1 \le N \le 100\,000$; $1 \le T \le 10^{10}$), the number of items and the upper limit. The second line contains $N$ integers $W_i$ ($1 \le W_i \le 100\,000$), the weight of each item. The third line contains $N$ integers $V_i$ ($1 \le V_i \le 100\,000$), the value of each item.

Print one integer on a line, the largest output the greedy algorithm can obtain.