No.3761 Moonlit Battle
レベル :
/ AI推定難易度 : 1950
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 :
ei1333333
/ テスター :
kyoprouno
ei13333333
タグ : / 解いたユーザー数 23
作問者 :
ei1333333
/ テスター :
kyoprouno
ei13333333
問題文最終更新日: 2026-10-09 00:25:22
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 517
(順位表)
の他の問題:
Problem Statement
An army of messengers has come from the Moon to take Kaguya back there.
There are $N$ types of messengers. There are $A_i$ messengers of type $i (1 \leq i \leq N)$, and each of them initially has $B_i$ health.
Kaguya can perform the following $2$ types of actions any number of times, in any order.
- Decrease the health of every messenger by $1$.
- Choose $1$ messenger and decrease that messenger's health by $D$.
Find the minimum number of actions required to make the health of every messenger $0$ or less.
Constraints
- $1 \leq N \leq 3 \times 10^5$
- $1 \leq D \leq 10^9$
- $1 \leq A_i, B_i \leq 10^9$
- All input values are integers.
Input
$N$ $D$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_N$ $B_N$
Output
Print the answer on $1$ line.
Sample
Sample 1
Input
2 3 2 4 1 7
Output
5
By performing $5$ actions as follows, the health of every messenger can be made $0$ or less.
- Perform action $1$. The health values of the messengers of type $1$ become $(3,3)$, and the health value of the messenger of type $2$ becomes $(6)$.
- For the $2$ messengers of type $1$, perform action $2$ on each of them $1$ time.
- For the $1$ messenger of type $2$, perform action $2$ $2$ times.
It is impossible to make the health of every messenger $0$ or less with $4$ or fewer actions, so the answer is $5$.
Sample 2
Input
3 5 1 2 3 6 2 11
Output
8
Sample 3
Input
1 10 100 9
Output
9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。