Postman

A postman delivers letters to his neighbors in a one-dimensional world.

The post office, which contains all of the letters to begin with, is located at $x = 0$x=0, and there aren houses to which the postman needs to deliver the letters. House $i$i is located at position $x_i$xi​, andthere are mi letters that need to be delivered to this location. But the postman can only carry kletters at once.

The postman must start at the post office, pick up some number of letters less than or equal to hiscarrying capacity, and then travel to some of the houses dropping off letters. He must then returnto the post office, repeating this process until all letters are delivered. At the end he must returnto the post office.

The postman can travel one unit of distance in one unit of time.

What is the minimum amount of time it will take the postman to start at the post office, deliverall the letters, and return to the post office?

Input

The first line of input contains two space-separated integers $n \ (1 ≤ n ≤ 1,000)$n (1≤n≤1,000) and $k \ (1 ≤ k ≤ 10^7)$k (1≤k≤107).

Each of the next n lines contains two space-separated integers $x_i (|x_i| ≤ 10^7)$xi​(∣xi​∣≤107)and $m_i (1 ≤ m_i ≤ 10^7)$mi​(1≤mi​≤107).

Output

Print, on a single line, the minimum amount of time it will take to complete the mail delivery route.

样例输入1
4 10
-7 5
-2 3
5 7
9 5
样例输出1
42
样例输入2
7 1
9400000 10000000
9500000 10000000
9600000 10000000
9700000 10000000
9800000 10000000
9900000 10000000
10000000 10000000
样例输出2
1358000000000000

贪心，先送远的再送近的。

#include<bits/stdc++.h>

#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scahf("%c",&a);
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 1e3 + 10;
pii a1[N], a2[N];
int n, k, t1, t2;

int main() {
    n = qr(), k = qr();
    repi(i, 1, n) {
        int x = qr(), m = qr();
        if (x < 0)a1[++t1] = {x, m};
        else a2[++t2] = {x, m};
    }
    sort(a1 + 1, a1 + 1 + t1), sort(a2 + 1, a2 + 1 + t2, greater<pii >());
    int now = 0;
    ll ans = 0;
    while (now < t1) {
        if (a1[now + 1].se >= k) {
            ans -= 2ll * a1[now + 1].fi * (a1[now + 1].se / k), a1[now + 1].se %= k;
            if (!a1[now + 1].se)now++;
        }
        ans -= a1[now + 1].fi * 2ll;
        ll sum = 0;
        while (now + 1 <= t1 && sum + a1[now + 1].se <= k)sum += a1[++now].se;
        if (now + 1 <= t1)a1[now + 1].se -= (k - sum);
    }
    now = 0;
    while (now < t2) {
        if (a2[now + 1].se >= k) {
            ans += 2ll * a2[now + 1].fi * (a2[now + 1].se / k), a2[now + 1].se %= k;
            if (!a2[now + 1].se)now++;
        }
        ans += a2[now + 1].fi * 2ll;
        ll sum = 0;
        while (now + 1 <= t2 && sum + a2[now + 1].se <= k)sum += a2[++now].se;
        if (now + 1 <= t2)a2[now + 1].se -= (k - sum);
    }
    pl(ans);
    return 0;
}