SP9378 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 atmost once. 2\) The sum of the costs of all the operations performed must be

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 a single integer V such that all the plots have atleast height V.