그리디 배낭 문제

부디는 대학교 수업에서 배운 고전적인 0-1 배낭 문제를 우연히 다시 보게 되었다. 아이템은 1번부터 $N$번까지 $N$개가 있다. $i$번 아이템은 양의 무게 $W_i$와 양의 가치 $V_i$를 가진다. 목표는 아이템을 0개 이상 골라 무게 합이 $M$을 넘지 않으면서 가치 합을 최대로 만드는 것이다.

부디는 한동안 이 문제를 풀지 않아서 해법이 기억나지 않았다. 그래서 그리디 알고리즘을 고안했다. 이 알고리즘은 1번 아이템부터 $N$번 아이템까지 차례로 확인한다. $i$번 아이템을 넣어도 무게 합이 $M$을 넘지 않으면 그 아이템을 고르고, 그렇지 않으면 건너뛴다. 출력은 고른 아이템 가치의 합이다.

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

부디도 이 그리디 알고리즘이 최적해를 항상 찾지는 못한다는 것을 알고 있지만, 지금은 개의치 않는다. 출력이 $M$에 따라 크게 달라진다는 점에 주목한 그는 $M$을 1부터 주어진 상한 $T$까지 바꿔 가며 그리디 알고리즘을 실행하고, 얻을 수 있는 출력의 최댓값을 구하려고 한다.

예를 들어 $N = 5$, $T = 10$, $W_{1..5} = \{10, 1, 2, 3, 4\}$, $V_{1..5} = \{1, 1, 1, 1, 1\}$인 경우를 보자. 얻을 수 있는 출력의 최댓값은 3이며, 예를 들어 $M = 6$일 때 나온다. 그리디 알고리즘은 2번, 3번, 4번 아이템을 고르고, 무게 합은 $1 + 2 + 3 = 6$, 가치 합은 $1 + 1 + 1 = 3$이 된다. $M = 10$이면 1번 아이템만 고르며, 무게 합은 10, 가치 합은 1이다.

당신의 임무는 $M$을 1부터 $T$까지 바꿔 가며 그리디 알고리즘이 얻을 수 있는 출력의 최댓값을 구하는 것이다.

첫 줄에 두 정수 $N$과 $T$가 주어진다 ($1 \le N \le 100\,000$; $1 \le T \le 10^{10}$). $N$은 아이템의 개수이고 $T$는 $M$의 상한이다. 둘째 줄에는 각 아이템의 무게 $W_i$ ($1 \le W_i \le 100\,000$) $N$개가, 셋째 줄에는 각 아이템의 가치 $V_i$ ($1 \le V_i \le 100\,000$) $N$개가 주어진다.

얻을 수 있는 출력의 최댓값을 정수 한 개로 한 줄에 출력한다.