No.1297 Bronze Statues
Problem Statement
Island 1, Island 2, ..., Island $N$ are lined up in the east-west direction.
The ruler of these islands has decided to build one bronze statue of himself on every island.
There are $N$ artisans who can build statues, and the $i$-th artisan (hereafter Artisan $i$) lives on Island $i$.
When the ruler requests Artisan $i$ to build a statue on Island $j$, the following three types of costs are incurred.
-
Labor cost
- $a_i$ yen is charged each time a request is made.
-
Design cost
- $b_i$ yen is charged only the first time Artisan $i$ is requested.
-
Transportation cost
-
If $i \ne j$, $|i-j| \times C$ yen is charged.
-
If $i \ne j$, $|i-j| \times C$ yen is charged.
Input
$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}$
- All inputs are integers.
Output
Output the answer. Print a newline at the end.
Sample
Sample 1
Input
4 2 3 4 2 2 3 2 5 1
Output
18
By making requests as follows, statues are built on all islands for 18 yen.
- Have Artisan 2 build a statue on Island 1. This costs 2 yen for labor, 2 yen for design, and |2-1|$\times$2=2 yen for transportation.
- Have Artisan 2 build a statue on Island 2. This costs 2 yen for labor.
- Have Artisan 3 build a statue on Island 3. This costs 3 yen for labor and 2 yen for design.
- Have Artisan 3 build a statue on Island 4. This costs 3 yen for labor and |3-4|$\times$2=2 yen for transportation.
Sample 2
Input
5 1 1000 1000 1 1 1000 1000 1000 1000 1000 1000
Output
13
Clearly, the artisan living on Island 2 is a better deal than the other artisans.
If statues are requested in the order of Islands 1, 2, 3, 4, 5,
the costs are 3 yen, 1 yen, 2 yen, 3 yen, and 4 yen, respectively.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
沙耶花
tatyam