Є $n$ солдатів, які стоять у ряд. Спочатку солдат із номером $i$ має $a_i$ одиниць здоров’я.

Ви можете здійснити кілька атак або не здійснювати жодної. Під час кожної атаки ви можете вибрати відрізок $[l,r]$ ($1\le l\le r\le n$) і зменшити здоров’я всіх солдатів із номерами на цьому відрізку на $1$. Кожна атака коштує $m$.

Після завершення всіх атак, якщо здоров’я солдата з номером $i$ не перевищує $0$, ви отримуєте винагороду $b_i$. Серед солдатів є як вороги, так і союзники, тому $b_i$ може бути від’ємним. Зверніть увагу, що винагорода за кожного солдата нараховується лише один раз.

Знайдіть план атак, який максимізує суму винагород мінус сумарні витрати. Формально, нехай у вашому плані здійснено $k$ атак, а остаточне здоров’я солдата з номером $i$ дорівнює $c_i$. Нехай $p_i$ дорівнює $1$, якщо $c_i\le0$, і $0$ інакше. Тоді потрібно максимізувати $\left(\sum_{i=1}^{n}p_i\times b_i\right)-m\times k$. Вивести потрібно лише найбільшу можливу різницю між сумою винагород і сумарними витратами.

Вхідні дані

Зчитайте дані з файлу soldier.in.

У цій задачі є кілька наборів тестових даних.

Перший рядок містить додатне ціле число $T$ — кількість наборів даних.

Далі послідовно задано набори тестових даних. Для кожного набору:

Перший рядок містить два цілі числа $n,m$ — кількість солдатів і вартість однієї атаки відповідно.

Кожен із наступних $n$ рядків містить два цілі числа $a_i,b_i$ — здоров’я та винагороду для відповідного солдата.

Вихідні дані

Виведіть відповідь у файл soldier.out.

Для кожного набору даних виведіть в окремому рядку одне ціле число — найбільшу можливу різницю між сумою винагород і сумарними витратами серед усіх планів.

Приклади

Вхідні дані 1

3
5 1
1 3
2 5
1 4
3 3
5 1
3 2
1 5
1 -100
1 5
3 2
1 5
1 -1
1 5

Вихідні дані 1

12
6
7

Пояснення

У першому наборі даних один з оптимальних планів складається з трьох атак на відрізки $[1,5],[2,4],[4,4]$ відповідно. Остаточна послідовність здоров’я дорівнює $(0,0,-1,0,4)$, винагорода становить $b_1+b_2+b_3+b_4=15$, а витрати — $3\times1=3$. Можна довести, що кращого плану немає, тому відповідь дорівнює $15-3=12$.

У другому наборі даних один з оптимальних планів складається з двох атак на відрізки $[1,1],[3,3]$ відповідно.

У третьому наборі даних один з оптимальних планів складається з однієї атаки на відрізок $[1,3]$.

Підзадачі

Нехай $\sum n$ позначає суму значень $n$ за всіма наборами даних в одному тестовому файлі. Для всіх тестових даних гарантовано:

• $1\le T\le5\times10^5$;

• $1\le n,\sum n\le5\times10^5$, $1\le m\le10^9$;

• Для всіх $1\le i\le n$: $1\le a_i\le10^9$, $-10^9\le b_i\le10^9$.