题目描述

皮卡丘有 \(n\) 个好朋友，每个好朋友在第 \(a_i\) 天可以教他 \(b_i\) 种技能，但是如果皮卡丘在 \(2\) 天之内（第 \(a_i\) 和 \(a_i+1\) 天）还没有学习这个技能的话，他的朋友就会失去耐心，收回这个技能，并且保持生气状态一个礼拜。皮卡丘每天最多能学习 \(v\) 个技能，现在计算他最多可以学到多少技能。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；每组数据中，第一行为两个正整数 \(n\) 和 \(v\)，接下来 \(n\) 行，每行两个正整数 \(a_i\) 和 \(b_i\)。所有输入不超过 \(3000\)。

输出格式

对于每组数据，输出皮卡丘总共能够学到的最大技能数。

样例1

样例输入1

2
2 3
1 5
2 3
5 10
3 20
2 20
1 20
4 20
5 20

样例输出1

8
60

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T3\)