D - 倉庫からの荷物配送 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は配送センターで働いており、倉庫から N 軒の届け先に荷物を配送しなければなりません。

倉庫と全ての届け先は一本の数直線上にあります。倉庫は座標 0 の位置にあり、i 番目の届け先は座標 X_i の位置にあります（X_i は正または負の値をとりえます）。全ての届け先の座標は互いに異なり、倉庫の位置（座標 0）とも異なります。i 番目の届け先にはちょうど D_i 個の荷物を届ける必要があります。倉庫には最初から全ての届け先分の荷物、すなわち合計 \sum_{i=1}^{N} D_i 個の荷物が用意されています。

高橋君が使う台車には容量の制限があり、一度に最大 K 個の荷物しか積むことができません。高橋君は以下の手順を、全ての届け先に必要な個数の荷物を届け終わるまで繰り返します。

  1. 荷物を積む： 倉庫（座標 0）で台車に荷物を 1 個以上 K 個以下の好きな個数だけ積む。ただし、全ての届け先に対する未配送の荷物の残り個数の合計を超えて積むことはできない。
  2. 配送する： 倉庫を出発し、数直線上を自由に移動して、台車に積んだ荷物を好きな届け先に好きな個数ずつ届ける。1回の配送で複数の届け先を回ることができ、正の方向と負の方向の届け先を混在して訪れることもできる。例えば、まず正の方向に進んでいくつかの届け先に届け、引き返して負の方向の届け先に届ける、といった経路も可能である。各届け先に届ける個数は、その届け先の未配送の残り個数以下でなければならない。台車に積んだ荷物を全て届けきる必要はなく、届けなかった荷物は倉庫に持ち帰り、次回以降の配送で改めて使うことができる。なお、配送の途中で倉庫（座標 0）を通過しても、追加で荷物を積むことはできない。
  3. 倉庫に戻る： 倉庫（座標 0）に戻る。

各届け先への配送は複数回に分けて行うことができます。例えば、5 個の荷物を届ける必要がある届け先に、ある回で 3 個、別の回で 2 個届けても構いません。

1回の配送における移動距離は、倉庫を出発してから倉庫に戻るまでに高橋君が実際に移動した距離の合計です。座標 a から座標 b へ移動するときの距離は |a - b| です。例えば、倉庫（座標 0）から座標 5 まで進み、引き返して座標 -3 まで進み、倉庫（座標 0）に戻った場合、移動距離は 5 + 8 + 3 = 16 です。

高橋君は、全ての荷物を届け終え、最終的に倉庫（座標 0）に戻ってくるまでの、全ての配送を通じた移動距離の合計をできるだけ短くしたいと考えています。

移動距離の合計の最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • -10^9 \leq X_i \leq 10^9
  • X_i \neq 0
  • X_i はすべて異なる
  • 1 \leq D_i \leq 10^9
  • \sum_{i=1}^{N} D_i \leq 10^9
  • 入力はすべて整数である

入力

N K
X_1 D_1
X_2 D_2
\vdots
X_N D_N

1 行目には、届け先の軒数 N と、台車に一度に積める荷物の最大個数 K がスペース区切りで与えられる。続く N 行のうち i 行目には、i 番目の届け先の座標 X_i と、その届け先に届ける必要がある荷物の個数 D_i がスペース区切りで与えられる。

出力

全ての荷物を届け終えて倉庫（座標 0）に戻るまでの、移動距離の合計の最小値を 1 行で出力せよ。

入力例 1

3 3
2 2
-4 1
5 2

出力例 1

22

入力例 2

2 2
-3 3
-1 1

出力例 2

12

入力例 3

8 5
-10 4
7 3
-2 6
15 2
4 5
-6 1
12 7
-14 3

出力例 3

128

入力例 4

20 7
-100 8
35 3
-12 15
80 6
5 9
-55 4
120 11
-3 2
60 7
-200 5
18 13
-75 10
150 1
-30 6
95 14
-140 3
42 8
-8 12
210 4
-180 9

出力例 4

3366

入力例 5

1 1000000000
-1000000000 1000000000

出力例 5

2000000000

Score : 400 pts

Problem Statement

Takahashi works at a delivery center and must deliver packages from a warehouse to N destinations.

The warehouse and all destinations are located on a single number line. The warehouse is at coordinate 0, and the i-th destination is at coordinate X_i (X_i can be positive or negative). All destination coordinates are distinct from each other and also distinct from the warehouse position (coordinate 0). Exactly D_i packages must be delivered to the i-th destination. The warehouse initially has all packages for all destinations, totaling \sum_{i=1}^{N} D_i packages.

The cart Takahashi uses has a capacity limit and can carry at most K packages at a time. Takahashi repeats the following procedure until the required number of packages has been delivered to all destinations:

  1. Load packages: At the warehouse (coordinate 0), load any number of packages from 1 to K onto the cart. However, he cannot load more than the total remaining number of undelivered packages across all destinations.
  2. Deliver: Depart from the warehouse and move freely along the number line, delivering packages from the cart to any destinations in any quantities. Multiple destinations can be visited in a single delivery trip, and destinations in both the positive and negative directions can be visited in the same trip. For example, a route where he first goes in the positive direction to deliver to some destinations, then turns back to deliver to destinations in the negative direction, is possible. The number of packages delivered to each destination must not exceed the remaining undelivered count for that destination. It is not necessary to deliver all packages loaded on the cart; undelivered packages are brought back to the warehouse and can be used in subsequent deliveries. Note that even if he passes through the warehouse (coordinate 0) during a delivery trip, he cannot load additional packages.
  3. Return to warehouse: Return to the warehouse (coordinate 0).

Deliveries to each destination can be split across multiple trips. For example, if 5 packages need to be delivered to a destination, it is acceptable to deliver 3 in one trip and 2 in another.

The travel distance of a single delivery trip is the total distance Takahashi actually travels from departing the warehouse until returning to the warehouse. The distance of moving from coordinate a to coordinate b is |a - b|. For example, if he goes from the warehouse (coordinate 0) to coordinate 5, turns back to coordinate -3, and returns to the warehouse (coordinate 0), the travel distance is 5 + 8 + 3 = 16.

Takahashi wants to minimize the total travel distance across all delivery trips until all packages are delivered and he has returned to the warehouse (coordinate 0).

Find the minimum total travel distance.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • -10^9 \leq X_i \leq 10^9
  • X_i \neq 0
  • All X_i are distinct
  • 1 \leq D_i \leq 10^9
  • \sum_{i=1}^{N} D_i \leq 10^9
  • All inputs are integers

Input

N K
X_1 D_1
X_2 D_2
\vdots
X_N D_N

The first line contains the number of destinations N and the maximum number of packages K that can be loaded on the cart at once, separated by a space. The i-th of the following N lines contains the coordinate X_i of the i-th destination and the number of packages D_i that need to be delivered there, separated by a space.

Output

Print in one line the minimum total travel distance until all packages have been delivered and Takahashi has returned to the warehouse (coordinate 0).

Sample Input 1

3 3
2 2
-4 1
5 2

Sample Output 1

22

Sample Input 2

2 2
-3 3
-1 1

Sample Output 2

12

Sample Input 3

8 5
-10 4
7 3
-2 6
15 2
4 5
-6 1
12 7
-14 3

Sample Output 3

128

Sample Input 4

20 7
-100 8
35 3
-12 15
80 6
5 9
-55 4
120 11
-3 2
60 7
-200 5
18 13
-75 10
150 1
-30 6
95 14
-140 3
42 8
-8 12
210 4
-180 9

Sample Output 4

3366

Sample Input 5

1 1000000000
-1000000000 1000000000

Sample Output 5

2000000000