Problem Description

Country LQ has $n$ cities, numbered from $0$ to $n - 1$. Between every pair of these $n$ cities, there is exactly one bidirectional road, which means any two cities are reachable from each other. Each road has an attribute $D$, representing the dust level of this road. When traveling from city A to city B, there may be multiple routes. The dust level of a route is defined as the sum of the dust levels of all roads on that route. People in Country LQ hate dust, so they always choose the route with the minimum dust level.

Country LQ cares a lot about residents' travel environment. They use an indicator $P$ to measure the travel environment of Country LQ, where $P$ is defined as:

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

Here, $d(i,j)$ denotes the dust level of the minimum-dust route from city $i$ to city $j$.

To improve the travel environment, every city must take action. When a city improves roads, it reduces the dust level of all roads directly connected to this city by $1$. However, each road has a lower bound dust level $L$. When the dust level reaches this lower bound, no matter how much more improvement is done, the dust level of the road will not decrease any further.

The plan is as follows:

• On day $1$, city $0$ improves the environment of roads directly connected to it.
• On day $2$, city $1$ improves the environment of roads directly connected to it.

……

• On day $n$, city $n - 1$ improves the environment of roads directly connected to it.
• On day $n + 1$, city $0$ improves the environment of roads directly connected to it.
• On day $n + 2$, city $1$ improves the environment of roads directly connected to it.

……

Country LQ wants to make the indicator $P$ satisfy $P \leq Q$. Find the minimum number of days needed so that $P \leq Q$ can be satisfied. If it already satisfies the condition initially, output $0$. If it can never be satisfied, output $-1$.

Input Format

The first line contains two integers $n, Q$, separated by a space, representing the number of cities and the target value for the indicator $P$.

The next $n$ lines each contain $n$ integers, with a space between adjacent integers. The value in row $i$, column $j$ is $D_{i,j}$ $(D_{i,j}=D_{j,i},D_{i,i} = 0)$, representing the dust level of the road directly connecting city $i$ and city $j$.

The next $n$ lines each contain $n$ integers, with a space between adjacent integers. The value in row $i$, column $j$ is $L_{i,j}$ $(L_{i,j} = L_{j,i}, L_{i,i} = 0)$, representing the lower bound dust level of the road directly connecting city $i$ and city $j$.

Output Format

Output one line containing one integer, representing the answer.

3 10
0 2 4
2 0 1
4 1 0
0 2 2
2 0 0
2 0 0

2

Hint

[Sample Explanation]

The initial graph is shown below, and the number on each edge represents the dust level of that road:

At this time, the dust levels of the minimum-dust routes between each pair of vertices are:

• $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3$;
• $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1$;
• $d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0$.

The initial indicator $P$ is $(2 + 3 + 1) \times 2 = 12$, which does not satisfy $P \leq Q = 10$.

On the first day, city $0$ improves the roads, and the updated graph is shown below:

Note that the value of edge $(0, 2)$ decreases by $1$, but $(0, 1)$ does not decrease, because $L_{0,1} = 2$, so the value of $(0, 1)$ cannot be decreased any further. At this time, the dust levels of the minimum-dust routes between each pair of vertices are:

• $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3$,
• $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1$,
• $d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0$.

At this time, $P$ is still $12$.

On the second day, city $1$ improves the roads, and the updated graph is shown below:

At this time, the dust levels of the minimum-dust routes between each pair of vertices are:

• $d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2$,
• $d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0$,
• $d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0$.

The indicator $P$ at this time is $(2 + 2) \times 2 = 8 < Q$, so the condition is satisfied.

Therefore, the answer is $2$.

[Constraints and Notes]

• For $30\%$ of the testdata, $1 \leq n \leq 10$, $0 \leq L_{i,j} \leq D_{i,j} \leq 10$.
• For $60\%$ of the testdata, $1 \leq n \leq 50$, $0 \leq L_{i,j} \leq D_{i,j} \leq 10^5$.
• For all testdata, $1 \leq n \leq 100$, $0 \leq L_{i,j} \leq D_{i,j} \leq 10^5$, $0 \leq Q \leq 2^{31} - 1$.

Lanqiao Cup 2022 National Contest, Group A, Problem F.

Translated by ChatGPT 5