PepperLa is good at dealing with string problems, so he's going to offer string algorithm courses.
PepperLa has set up $N$ class rooms, there's one road between every two class rooms, and each road is equal in length.
PepperLa is afraid of the dark, so he only walks on roads with the light on. At the beginning, there is no light on. PepperLa has to pay one dollar for lighting the light of a road. However, PepperLa is dreaming of buying himself a switch, so he would like to pay the least.
The courses are scheduled so tightly that PepperLa can't afford to waste his time. So the distance between two class room should not be too far away. Specifically, you need to light the fewest roads so that the shortest distance between class room $i$ and class room $j$ should eaqual to $d i s [ i ] [ j ]$.(the distance means the total length of the path)
Please tell PeoperLa how much is the minimum he has to pay.
There are multiple test cases in this problem.
For every test case, The first line has 1 interger, $N (1 <= N <= 10^3)$
The next $N$ lines each line contains $N$ interger, the interger in $i$'th row, $j$'th column is $d i s [ i ] [ j ] (1 <= d i s [ i ] [ j ] <= 10^6)$
The input guarantees that the data given is legal and there's always a solution
$d i s [ i ] [ j ] = d i s [ j ] [ i ], d i s [ i ] [ i ] = 0, sum N <= 5 times 10^3$
For each test case, output a single line contains one integer,representing for the minimal money PepperLa has to pay.
Light the light of road (1,2),(2,3)
## Input
There are multiple test cases in this problem.For every test case, The first line has 1 interger, $N (1 <= N <= 10^3)$The next $N$ lines each line contains $N$ interger, the interger in $i$'th row, $j$'th column is $d i s [ i ] [ j ] (1 <= d i s [ i ] [ j ] <= 10^6)$The input guarantees that the data given is legal and there's always a solution$d i s [ i ] [ j ] = d i s [ j ] [ i ], d i s [ i ] [ i ] = 0, sum N <= 5 times 10^3$
## Output
For each test case, output a single line contains one integer,representing for the minimal money PepperLa has to pay.
[samples]
## Note
Light the light of road (1,2),(2,3)
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of horizontal segments.
Each segment $ i $ is defined by $ (L_i, R_i, Y_i) $, representing a horizontal line segment from $ (L_i, Y_i) $ to $ (R_i, Y_i) $, with $ L_i < R_i $ and $ Y_i > 0 $.
The ball starts at $ (0, 0) $ with initial velocity $ (1, 1) $, so its trajectory at time $ t $ is $ (t, t) $, until it intersects a segment.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq L_i, R_i, Y_i \leq 10^9 $, $ L_i < R_i $
3. Segments are pairwise disjoint (no shared points, including endpoints).
**Objective**
Simulate the ball’s trajectory:
- The ball moves along the line $ y = x $.
- When it intersects a segment $ i $ at point $ (x, y) = (y_i, y_i) $, provided $ L_i \leq y_i \leq R_i $, a collision occurs:
- The segment disappears.
- The vertical velocity reverses: new velocity becomes $ (1, -1) $.
- After collision, the ball continues along the new direction $ y - y_i = -(x - y_i) $, i.e., $ y = -x + 2y_i $.
- Subsequent intersections are checked with remaining segments.
- Count the total number of collisions (segments hit) before the ball exits the first quadrant or no more intersections occur.
**Goal**: Compute the maximum number of segments the ball can hit along its piecewise-linear path.