Dust Reduction Route Problem

LQ country has n cities numbered from 0 to n-1. Every pair of different cities is connected by exactly one bidirectional road. Each road has a dust value D and when traveling from city A to city B one may choose any route; however, the dust of a route is defined as the sum of the dust values on all roads along the route. Since the citizens hate dust, they always choose the route with the minimum total dust. In this complete graph the optimal route between two different cities is always the direct road connecting them.

The travel environment of LQ country is measured by an index P defined as:

$$P = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} d(i,j),$$

where d(i,j) is the minimum dust value on any route between cities i and j (with d(i,i)=0).

To improve the travel environment, every city carries out improvements on the roads directly connected to it. When a city performs an improvement, the dust value on every road connected to that city is decreased by 1, but no road’s dust can drop below a given lower bound L (i.e. if a road's dust is L, it remains L no matter how many improvements are applied).

The improvement plan is as follows:

• Day 1: City 0 improves all roads connected to it.
• Day 2: City 1 improves its adjacent roads.
• ...
• Day n: City n-1 improves its adjacent roads.
• Day n+1: City 0 improves again,
• Day n+2: City 1 improves again,
• and so on.

After a given number of days, the dust on the road connecting cities i and j becomes:

$$d(i,j)= \max\Bigl(L,~D_{ij} - (c_i + c_j)\Bigr),$$

where c_i is the number of times city i has performed an improvement. Note that for a given day d, if city i gets its first improvement on day i+1 and then every n days thereafter, then:

$$c_i = \begin{cases} 0, & d < i+1,\\ \left\lfloor\frac{d-i-1}{n}\right\rfloor+1, & d \ge i+1. \end{cases} $$

The environment index P after improvements is:

$$P = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\,d(i,j).$$

LQ country wants to achieve P ≤ Q. Your task is to determine the minimum number of days required so that P ≤ Q. If the condition is already satisfied initially, output 0. If it is impossible to ever achieve, output -1.

inputFormat

The first line contains three integers n, Q, and L (number of cities, target index, and dust lower bound).

Then follow n-1 lines. For i from 1 to n-1, the i-th line contains i integers. The j-th number on that line (0-indexed) represents the initial dust value Di,j on the road connecting city i and city j. Roads are bidirectional, so Di,j = Dj,i for all i ≠ j.

outputFormat

Output a single integer indicating the minimum number of days required so that P ≤ Q. If the condition is initially satisfied, output 0. If it is impossible to achieve, output -1.

sample

3 12 1
3
4 5

3