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.

题目描述

玥玥有无限张价值 𝑚 的奶茶代金券，每次玥玥会使用代金券购买两杯奶茶。只有当代金券的总价值大于等于奶茶的总价值才可以购买，但是奶茶店是不找零的。

假设每张代金券价值 10 元，然后买了一杯 11 元和一杯 4 元的奶茶。则需要两张代金券才能购买，但是两张代金券价值 20，奶茶总价值 15，即我们可以认为玥玥这样做浪费了 5 元。 现在已知玥玥总共购买了 𝑛 种价值的奶茶，第 𝑖 种奶茶购买的数量为 $𝑎_𝑖$，价格为 $𝑏_𝑖$。请问玥玥最少浪费多少钱？

输入格式

输入第一行包含两个正整数 𝑛, 𝑚，表示共有 𝑛 条信息，每张代金券价值 𝑚元。 (1 ≤ 𝑛 ≤ $10^5$, 1 ≤ 𝑚 ≤ $10^9$ )

接下来 𝑛 行每行包含两个正整数 $𝑎_𝑖, 𝑏_i(1 ≤ 𝑎_𝑖, 𝑏_𝑖 ≤ 10^9)$，保证给出的所有 $𝑏_𝑖$ 不会重复，且所有 𝑎 之和为一个小于 $10^9$ 的偶数。

输出格式

输出一行一个整数表示最少浪费的钱数。

3 10
2 21
1 18
1 20

10

提示与说明

样例1

注意，不能一次购买两杯 21 元的奶茶和一杯 18 元的奶茶，因为每次只能购买两杯奶茶，所以只能用四张优惠券购买一杯 21 元的奶茶和一杯 18 元的奶茶， 浪费 40 − 21 − 18 = 1 元，再用 5 张优惠券购买一杯 21 元和一杯 20 元的 奶茶，浪费 9 元，共浪费 1 + 9 = 10 元。

对于 1 − 3 测试点，有 $1 ≤ 𝑛 ≤ 10^3$ 对于 4 − 6 测试点，有 $\frac{m}{2} ≤ 𝑏_𝑖 ≤ 𝑚$ 对于 100% 的数据，有$1 ≤ 𝑛 ≤ 10^5, 1 ≤ 𝑚 ≤ 10^9$