103035: [Atcoder]ABC303 F - Damage over Time

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $525$ points

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

Input

题意翻译

有一只血量为 $H$ 的怪兽,你现在要攻击它。你有 $N$ 种方式可以攻击它。 如果你在时间 $j$ 用了第 $i$ 种方式攻击,那么在时间 $j,j+1,\cdots j+t_i-1$,它都会受到 $d_i$ 点伤害。 问最少需要花多少时间才能使怪兽的血量不高于 $0$。

Output

得分:$525$分 部分 问题描述 一只生命值为$H$的怪物出现在你面前,一场回合制战斗开始了。 在每个回合$1,2,…$,你施放其中一个$N$个法术,法术$1,…,N$。 如果你在回合$j$施放法术$i$,怪物的生命值在每个回合$j,j+1,…,j+t_i -1$都会减少$d_i$。 找出你能让怪物的生命值为$0$或更低的最早的回合。 部分 约束 * $1 \leq N \leq 3 \times 10^5$ * $1 \leq H \leq 10^{18}$ * $1 \leq t_i,d_i \leq 10^9$ * 输入中的所有值都是整数。 部分 输入 输入按照以下格式从标准输入给出: $N$ $H$ $t_1$ $d_1$ $\vdots$ $t_N$ $d_N$ 部分 输出 打印答案。 部分 样例输入 1 ``` 2 20 2 2 5 1 ``` 部分 样例输出 1 ``` 6 ``` 以下程序可以在第6个回合让怪物的生命值为0或更低,这是最早的回合。 * 在第1个回合施放法术$1$。由于在第1个回合施放的法术,怪物的生命值减少2,变为$18$。 * 在第2个回合施放法术$2$。由于在第1个和第2个回合施放的法术,怪物的生命值减少$2+1=3$,变为$15$。 * 在第3个回合施放法术$1$。由于在第2个和第3个回合施放的法术,怪物的生命值减少$1+2=3$,变为$12$。 * 在第4个回合施放法术$2$。由于在第2,3和第4个回合施放的法术,怪物的生命值减少$1+2+1=4$,变为$8$。 * 在第5个回合施放法术$1$。由于在第2,4和第5个回合施放的法术,怪物的生命值减少$1+1+2=4$,变为$4$。 * 在第6个回合施放法术$2$。由于在第2,4,5和第6个回合施放的法术,怪物的生命值减少$1+1+2+1=5$,变为$-1$。 部分 样例输入 2 ``` 10 200 1 21 1 1 1 1 8 4 30 1 3 1 10 2 8 1 9 1 4 4 ```

加入题单

上一题 下一题 算法标签: