Score : $525$ points

问题陈述

一个拥有 $H$ 点生命值的怪物出现在你面前，一场回合制战斗开始了。

在每个回合 $1,2,\dots$ 中，你可以施放 $N$ 种法术中的任意一种，法术编号分别为 $1,\dots,N$。

若你在第 $j$ 回合施放了第 $i$ 个法术，则在回合 $j,j+1,\dots,j+t_i-1$ 中，怪物的生命值每回合减少 $d_i$ 点。

请找出最早可以在哪个回合使怪物的生命值降至 $0$ 或以下。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

A monster with health $H$ has appeared in front of you, and a turn-based battle has started.

In each turn $1,2,…$, you cast one of $N$ spells, spells $1,…,N$.

If you cast spell $i$ in turn $j$, the monster's health reduces by $d_i$ in each turn $j,j+1,…,j+t_i －1$.

Find the earliest turn that you can make the monster's health $0$ or less.

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq H \leq 10^{18}$
• $1 \leq t_i,d_i \leq 10^9$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $H$

$t_1$ $d_1$

$\vdots$

$t_N$ $d_N$

Output

Print the answer.

Sample Input 1

2 20
2 2
5 1

Sample Output 1

6

The following procedure makes the monster's health $0$ or less in turn $6$, which is the earliest.

• Cast spell $1$ in turn $1$. Due to the spell cast in turn $1$, the monster's health reduces by $2$ and becomes $18$.
• Cast spell $2$ in turn $2$. Due to the spells cast in turns $1$ and $2$, the monster's health reduces by $2+1=3$ and becomes $15$.
• Cast spell $1$ in turn $3$. Due to the spells cast in turns $2$ and $3$, the monster's health reduces by $1+2=3$ and becomes $12$.
• Cast spell $2$ in turn $4$. Due to the spells cast in turns $2,3$ and $4$, the monster's health reduces by $1+2+1=4$ and becomes $8$.
• Cast spell $1$ in turn $5$. Due to the spells cast in turns $2,4$ and $5$, the monster's health reduces by $1+1+2=4$ and becomes $4$.
• Cast spell $2$ in turn $6$. Due to the spells cast in turns $2,4,5$ and $6$, the monster's health reduces by $1+1+2+1=5$ and becomes $-1$.

Sample Input 2

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

Sample Output 2

9

update @ 2024/3/10 08:32:11