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:

  1. For each i, the operation can be performed at most once.
  2. 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

hide comments
2021-06-29 23:25:43 Anmol
nice problem !!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.