Guan has just recently bought a new HDB flat in Bishan, and currently lives there with his "best friend" Jiahai. One day, you decide to go visit them in their new HDB flat. This HDB flat has N floors, numbered 1 to N. The HDB flat also has L units each floor arranged from left to right in a row, and a corridor connecting all L units of that floor, numbered 1 to L. However, the staircases are designed very oddly in this new, experimental HDB block. On each floor i, Ti random staircases are placed in front of certain units that bring you up to the next floor.
As if this problem was not confusing enough, there are also weird coefficients you have to deal with. In particular, due to random obstructions and flower pots here and there, each floor has a "speed coefficient", labelled Si for each floor i. Travelling a certain distance on each floor i requires Si * (number of units travelled) units of time. It is guaranteed to be possible to reach Jiahai and Guan's unit.
Jiahai and Guan live on the rightmost unit of the top floor, aka unit L of floor N. You start off at unit 1 of floor 1. Help calculate the amount of time it will take to reach their unit.
The first line of input will contain two integers, N
The next N
lines of input will contain Ti
+ 2 integers, with the first two integers representing Si
and the next Ti
integers representing the units on that floor that have staircases in front of them. (floor N
will always have 0 staircases.)
The output should contain one line with one integer, the minimum amount of time it takes to reach Jiahai and Guan's house.
will not exceed 100.
Subtask 1 (16%): 1 ≤ N, L ≤ 100. There will be a total of at most 100 staircases.
Subtask 2 (19%): 1 ≤ N, L ≤ 1 000. There will be at most 50 staircases on each floor.
Subtask 3 (21%): 1 ≤ N, L ≤ 1 000. There will be a total of at most 1 000 staircases.
Subtask 4 (44%): 1 ≤ N, L ≤ 100 000. There will be a total of at most 500 000 staircases.
Subtask 5 (0%): Sample testcases.
Sample Input 1
2 2 3 6
9 1 5
3 1 3
Sample Output 1
Sample Input 2
5 2 3 6
7 2 2 4
9 3 3 4 5
Sample Output 2