7928번 - Artefakt 다국어

Niedawno, robiąc porządki w piwnicy, znalazłem przedmiot, który wygląda jak starożytny artefakt. Jest to olbrzymia szachownica, z tysiącami równych, malutkich pól. Po wielu godzinach obliczeń udało mi się stwierdzić, że szachownica ma n wierszy. Zauważyłem tylko, że w każdym wierszu (oznaczonym przez i) znajduje się jeden taki fragment, że pomiędzy a_i-tą oraz b_i-tą pionową linią, na każdym polu tego wiersza znajduje się złota płytka. Poza tym fragmentem, w danym wierszu wszystkie pozostałe pola są puste.

Do artefaktu dołączona była krótka instrukcja: Poszerz fragmenty zawierające złote płytki tak, aby k kolejnych kolumn było zapełnionych złotymi płytkami od góry do dołu. Jeśli Ci się to uda, czeka Cię niespodzianka. Bardzo chciałbym dowiedzieć się, jaka to niespodzianka, ale nie wiem, czy stać mnie na zakup wystarczającej liczby złotych płytek. Pomóż mi i napisz program, który wypisze minimalną liczbę płytek, którą muszę kupić.

W pierwszej linii wejścia znajduje się liczba całkowita d oznaczająca liczbę testów (1 ≤ d ≤ 100), później następuje d opisów testów.

W pierwszej linii każdego testu znajdują się liczby całkowite n (1 ≤ n ≤ 10⁵) oraz k (1 ≤ k ≤ 2 ∗ 10⁹). W drugim wierszu znajduje się n par liczb całkowitych a_i oraz b_i (0 ≤ a_i < b_i ≤ 10⁹), oznaczających numery pionowych linii, pomiędzy którymi ułożone są płytki. Szachownica ma 2∗10⁹ kolumn numerowanych od 1 do 2 ∗ 10⁹. Linia o numerze i rozdziela kolumny o numerach i − 1 oraz i.

Dla każdego testu wypisz liczbę złotych płytek, które muszę kupić.

Poniższy rysunek obrazuje test przykładowy. Czarne pola to te pola, na których płytki znajdowały się od początku. Szare pola pokazują minimalny zestaw pól, na które trzeba położyć płytki, tak aby w wyniku rozszerzenia fragmentów złożonych ze złotych płytek powstały 2 kolejne kolumny pełne złotych płytek.