LANDFILL - Landfill
You are given a sequence H[1], H[2] ... H[N] representing the initial heights of N pieces of land and an integer K. It costs C[i] Rupees to elevate each of H[i], H[i+1] ... H[i+K-1] by E[i]; if i+K > N, it will just elevate all the pieces of land from A[i] to A[N] - Let us call this an operation. The following constraints must be satisfied:
- For each i, the operation can be performed at most once.
- The sum of the costs of all the operations performed must be <= Budget.
You have to calculate the maximum height V such that each plot's elevation is at least V before you exhaust the budget.
Input
The first line of input contains 3 integers N, Budget and K.
The next N lines consists of 3 integers H[i], E[i] and C[i].
Output
Output a single integer V such that all the plots have at least height V.
Constraints
1 <= K <= 11
1 <= N <= 100
0 <= Budget, H[i], E[i], C[i] <= 1000000
Example
Input: 4 20 1 1 3 5 1 7 3 4 6 9 3 5 13 Output: 3
Explanation
You can raise the level of the (unit) segments 1, 2 and 3, yielding a sequence of final heights 4, 8, 10 and 3. The minimum height among these is 3.
Added by: | jack(chakradarraju) |
Date: | 2011-08-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Proposed by Anudhyan |