問題一覧 > 通常問題

No.3761 Moonlit Battle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 15
作問者 : ei1333333 / テスター : kyoprouno ei13333333
お気に入りにしたユーザー ProblemId : 14015 / 自分の提出
問題文最終更新日: 2026-10-09 00:25:22
yukicoder contest 517 (順位表) の他の問題:

問題文

かぐやを月に連れ戻すため、月から使者の軍勢がやってきました。

使者には $N$ 種類あります。種類 $i (1 \leq i \leq N)$ の使者は $A_i$ 人いて、それぞれの体力ははじめ $B_i$ です。

かぐやは、以下の $2$ 種類の行動を、好きな順番で何度でも行うことができます。

  1. すべての使者の体力を $1$ 減らす
  2. 使者 $1$ 人を選び、その使者の体力を $D$ 減らす

すべての使者の体力を $0$ 以下にするために必要な行動回数の最小値を求めてください。

制約

  • $1 \leq N \leq 3 \times 10^5$
  • $1 \leq D \leq 10^9$
  • $1 \leq A_i, B_i \leq 10^9$
  • 入力はすべて整数

入力

$N$ $D$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$

出力

$1$ 行に答えを出力せよ。

サンプル

サンプル1
入力
2 3
2 4
1 7
出力
5

次のように $5$ 回行動することですべての使者の体力を $0$ 以下にできます。

  • 行動 $1$ を行う。このとき、種類 $1$ の使者の体力はそれぞれ $(3,3)$、種類 $2$ の使者の体力は $(6)$ となる。
  • 種類 $1$ の使者 $2$ 人に対して、行動 $2$ をそれぞれ $1$ 回ずつ行う。
  • 種類 $2$ の使者 $1$ 人に対して、行動 $2$ を $2$ 回行う。

$4$ 回以下の行動ですべての使者の体力を $0$ 以下にすることはできないため、答えは $5$ です。

サンプル2
入力
3 5
1 2
3 6
2 11
出力
8

サンプル3
入力
1 10
100 9
出力
9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。