P15609 [ICPC 2021 Jakarta R] Greedy Knapsack

Budi stumbled upon the classical 0-1 Knapsack Problem that he has learned from his class in university. There are $N$ items numbered from $1$ to $N$. The $i^{th}$ item has a positive weight of $W_i$ and a positive value of $V_i$. The objective is to take zero or more items such that their total weight does not exceed $M$ while their total value is maximum. It has been a while since the last time Budi works on this problem, and he couldn't remember how to solve it. So, Budi devises a greedy algorithm in an attempt to solve this problem. The algorithm goes like this. Each item is processed one by one from the $1^{st}$ item to the $N^{th}$ item in sequential order. If the $i^{th}$ item can be taken such that the total weight does not exceed $M$, then you should take that item; otherwise, ignore it. Output the total value of all taken items. The greedy algorithm can be presented with the following pseudocode. ``` GreedyKnapsack(W[1..N], V[1..N], M): total_value = 0 total_weight = 0 for i = 1 to N: if total_weight + W[i]

Input begins with a line containing two integers $N$ $T$ ($1 \leq N \leq 100\,000$; $1 \leq T \leq 10^{10}$) representing the number of items and the upper limit, respectively. The second line contains $N$ integers $W_i$ ($1 \leq W_i \leq 100\,000$) representing the weight of the $i^{th}$ item. The third line contains $N$ integers $V_i$ ($1 \leq V_i \leq 100\,000$) representing the value of the $i^{th}$ item.

Output contains an integer in a line representing the largest output that can be obtained by the presented greedy algorithm.

#### Explanation for the sample input/output #2 You can set $M$ to be large enough such that all items can be taken, i.e. $M \geq 20$. #### Explanation for the sample input/output #3 The largest output can be obtained with $M = 17$. The $1^{st}$, $2^{nd}$, $4^{th}$, and $5^{th}$ will be taken with a total weight of $4 + 9 + 1 + 3 = 17$ and a total value of $203 + 175 + 218 + 304 = 900$.