You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定无限张价值 $m$ 的奶茶代金券，每次可以消耗若干张购买恰好两杯奶茶。只有当代金券的总价值不少于奶茶的总价值时才可以购买，但是奶茶店是不找零的。例如，若每张代金券价值 $10$ 元，则 需要两张代金券才能购买一杯 $11$ 元和一杯 $4$ 元的奶茶，定义这样做会浪费 $5$ 元。

现在需要购买 $n$ 种价格互不相同的奶茶，第 $i$ 种奶茶购买的数量为 $a_i$，价格为 $b_i$。求浪费总钱数的最小值。

输入格式

从文件 $milktea.in$ 中读入数据。

第一行两个正整数 $n, m$，表示需要购买 $n$ 种奶茶，每张代金券价值 $m$ 元。

接下来 $n$ 行，每行两个正整数 $a_i , b_i$，分别表示第 $i$ 种奶茶购买的数量与价格。

输出格式

输出到文件 $milktea.out$ 中。

一行一个非负整数表示浪费总钱数的最小值。

样例 1 输入：

3 10
2 21
1 18
1 20

样例 1 输出：

10

样例 1 解释：

用四张代金券购买一杯 $21$ 元的奶茶与一杯 $18$ 元的奶茶，浪费 $4 × 10 − 21 − 18 = 1$ 元。

用五张代金券购买一杯 $21$ 元的奶茶与一杯 $20$ 元的奶茶，浪费 $5 × 10 − 21 − 20 = 9$ 元。

共浪费 $1 + 9 = 10$ 元。可以证明，浪费的总钱数不会低于 $10$ 元。

样例 2 ：

见右侧文件下的 $milktea2.in$ 与 $milktea2.ans$。

数据范围

对于所有测试数据，保证 $1 ≤ n ≤ 10^5，1 ≤ m ≤ 10^9，1 ≤ a_i , b_i ≤ 10^9， ∑a_i ≤ 10^9，2 | ∑a_i$， 保证 $b_i$ 互不相同。

每个测试点的具体限制见下表：