After a certain mushroom-based AI startup released a tool that revolutionized how code is written, Johan got tired of his job. In light of the circumstances, he transitioned to a career as an adventurer. An adventurer’s primary duty is to kill monsters.

There are $N$ caves, numbered from $1$ to $N$. Every cave has a certain number of monsters standing in a line. Every monster has a specific strength and XP-value.

Johan starts with strength $1$ and only has access to cave $1$ in the beginning. To kill monsters, he can attack a cave. When he attacks he first targets the first monster. If he has atleast as much strength as the monster, then he wins, and his strength increases with the monsters XP. He then moves on to the next monster. If he ever loses a fight or defeats all the monsters, then he leaves the cave. When he leaves the cave, all the monsters come back as good as new. If he defeats all the monsters in cave $i$ and $i \neq N$, he unlocks cave $i+1$, and can attack it in the future.

His final goal is to be able to defeat the demon king, which he knows requires atleast $B$ strength. Determine the minimum number of attacks he needs to do get atleast $B$ strength.

Input

The first line of the input contains the integers $N$ and $B$ ($1 \leq N \leq 2 \cdot 10^5$, $1 \leq B \leq 10^9$), the number of caves and your goal strength.

Then come the descriptions of the $N$ caves. The description of each cave starts with a line which contains the integer $M$ ($1 \leq M \leq 3 \cdot 10^5$), the number of monsters in the cave. Then follow $M$ lines, each containing the integers $s$ and $e$ ($1 \leq s,e \leq 10^9$), strength and XP-value of a monster. They are presented in the same order in which you encounter the monsters inside the cave.

It is guaranteed that the first monster in the first cave has strength $1$. It is then always possible to achieve a strength of $B$.

Let $T$ be the sum of all $M$, so the total number of monsters. Then it holds that $1 \leq T \leq 3 \cdot 10^5$.

Output

Print one integer: the minumum number of attacks that Johan has to do to achieve a strength of $B$ or more.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Sample $1$

In sample $1$, Johan can attack cave $1$. Since he starts with strength $1$, he wins the fight and increases his strength with $1$. There aren’t more caves or monsters, and thus Johan never gets more than $1$ strength per attack. So, it takes $99$ attacks to get $B=100$ or more in strength.

Explanation of Sample $2$

Johan only has access to cave $1$ to start with. If he attacks it, then he defeats both the monsters and increases his strength with $3$. He also unlocks cave $2$, but cannot yet defeat the monster in it. If he attacks cave $1$ two more times, his strength becomes $10$. He can then attack cave $2$ two times to get $18$ strength, which is sufficient. It isn’t possible to do fewer attacks.

1 100
1
1 1

99

2 15
2
1 1
2 2
1
8 4

5

2 1000
2
1 1
2 2
2
7 4
200 1

211