루미 알고리즘

#1635플래티넘Grinding

PO 2026 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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 ≠ 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 ≤ N ≤ 2 · 10^5, 1 ≤ B ≤ 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 ≤ M ≤ 3 · 10^5), the number of monsters in the cave. Then follow M lines, each containing the integers s and e (1 ≤ s,e ≤ 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 ≤ T ≤ 3 · 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.

GroupPointsConstraints
110N, B, T ≤ 100
218N ≤ 2000, B, T ≤ 5000
320B ≤ 1000
415N=1
510Each cave has at most 10 monsters in it.
627No additional constraints.

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

입력
1 100
1
1 1
출력
99

예제 2

입력
2 15
2
1 1
2 2
1
8 4
출력
5

예제 3

입력
2 1000
2
1 1
2 2
2
7 4
200 1
출력
211

출처 표기

출처: Programmeringsolympiaden 2026년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.