問題一覧 > 通常問題

No.3761 Moonlit Battle

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 23
作問者 : ei1333333 / テスター : kyoprouno ei13333333
お気に入りにしたユーザー ProblemId : 14015 / 自分の提出
問題文最終更新日: 2026-10-09 00:25:22
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.

  1. Decrease the health of every messenger by $1$.
  2. 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もしくは右上の雲マークをクリックしてアカウントを作成してください。