hdb

Problem Description

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, T_i 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 S_i for each floor i. Travelling a certain distance on each floor i requires S_i * (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.

Input

The first line of input will contain two integers, N and L.
The next N lines of input will contain T_i + 2 integers, with the first two integers representing S_i and T_i and the next T_i integers representing the units on that floor that have staircases in front of them. (floor N will always have 0 staircases.)

Output

The output should contain one line with one integer, the minimum amount of time it takes to reach Jiahai and Guan's house.

Limits

S_i 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

4 7
2 2 3 6
9 1 5
3 1 3
5 0

Sample Output 1

45

Sample Input 2

4 8
5 2 3 6
7 2 2 4
9 3 3 4 5
2 0

Sample Output 2

25