問題一覧 > 通常問題

No.1297 銅像

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 5
作問者 : 沙耶花沙耶花 / テスター : tatyamtatyam
2 ProblemId : 4310 / 出題時の順位表
問題文最終更新日: 2020-11-21 19:15:06

問題文

島1, 島2, ..., 島$N$ が東西方向に並んでいます.
これらの島々の統治者は, すべての島に1体ずつ自らをかたどった銅像を建てることに決めました.

銅像を建てられる職人は $N$ 人存在して, $i$ 番目の職人 (以下職人 $i$ ) は島 $i$ に住んでいます.
統治者が職人 $i$ に対して島 $j$ に銅像を建てるよう依頼するとき, 以下の3種類の費用がかかります.

  • 作業費
    • 依頼を行うたびに $a_i$ 円かかります.
  • 設計費
    • 初めて職人 $i$ に依頼するときに限り, $b_i$ 円かかります.
  • 交通費
    • $i \ne j$ のとき, $|i-j| \times C$ 円かかります.
銅像をすべて建てるために最小で何円かかるでしょうか.

入力

$N \  C$
$a_1\ b_1$
$\vdots$
$a_N\ b_N$

  • $1 \le N \le 10^5$
  • $1 \le C \le 10^6$
  • $1 \le a_i,b_i \le 10^{12}$
  • 入力はすべて整数

出力

答えを出力してください. 最後に改行してください.

サンプル

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

次のように依頼をすると, すべての島に18円で銅像が建ちます.

  • 職人2に島1に銅像を建てさせる. 作業費として2円, 設計費として2円, 交通費として|2-1|$\times$2=2円かかる.
  • 職人2に島2に銅像を建てさせる. 作業費として2円かかる.
  • 職人3に島3に銅像を建てさせる. 作業費として3円, 設計費として2円かかる.
  • 職人3に島4に銅像を建てさせる. 作業費として3円, 交通費として|3-4|$\times$2=2円かかる.
サンプル2
入力
5 1
1000 1000
1 1
1000 1000
1000 1000
1000 1000
出力
13

明らかに, 島2に住む職人が他の職人に比べてお得です.
島1,2,3,4,5の順に銅像を建てるよう依頼するものとすると,
それぞれ3円, 1円, 2円, 3円, 4円かかります.

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