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 atmost 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 atleast 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 atleast 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.