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.