3740: 奶茶兑换券(第二轮02)
题目描述
玥玥有无限张价值 m 的奶茶代金券，每次玥玥会使用代金券购买两杯奶茶。只 有当代金券的总价值大于等于奶茶的总价值才可以购买，但是奶茶店是不找零的。 假设每张代金券价值 10 元，然后买了一杯 11 元和一杯 4 元的奶茶。则需要 两张代金券才能购买，但是两张代金券价值 20，奶茶总价值 15，即我们可以认 为玥玥这样做浪费了 5 元。
现在已知玥玥总共购买了 n 种价值的奶茶，第 i 种奶茶购买的数量为 ai ，价 格为 bi 。请问玥玥最少浪费多少钱？
输入
输入第一行包含两个正整数 n, m，表示共有 n 条信息，每张代金券价值 m 元。 (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9 )
接下来 n 行每行包含两个正整数 ai, bi (1 ≤ ai, bi ≤ 10^9)，保证给出的所有 bi 不会重复，且所有 a 之和为一个小于 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 ≤ n ≤ 10^3
对于 4 − 6 测试点，有 
m/2≤ bi ≤ m
对于 100% 的数据，有1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^9