10249: CF EDU - Two Pointer Method - Step 3 - E. Knapsack on a Segment
[Creator : ]
Description
Given an array of $n$ items, for each of them its weight is $w_i$ and cost is $c_i$. You need to select a segment of this array, the total weight on which is not more than $s$, and the total cost is maximum.
Input
The first line contains integers $n,s\ (1≤n≤10^5,\ 1≤s≤10^9)$.
The second line contains $n$ integers $w_i\ (1≤w_i≤10^9)$.
The third line contains $n$ integers $c_i\ (1≤c_i≤10^9)$.
The second line contains $n$ integers $w_i\ (1≤w_i≤10^9)$.
The third line contains $n$ integers $c_i\ (1≤c_i≤10^9)$.
Output
Print one number, the maximum total cost of items that can be put into a knapsack.
Sample 1 Input
6 20
9 7 6 5 8 4
7 1 3 6 8 3
Sample 1 Output
17