Sparing w Programowaniu Zespołowym Politechnika Poznańska, 13.03.2004

Opis

W każdym tramwaju znajduje się tabliczka opisująca trasę przejazdu tegoż tramwaju. Są na nią naniesione przystanki oraz czasy przejazdu pomiędzy kolejnymi przystankami zaokrąglone do minut. Jeśli chcemy obliczyć czas przejazdu pomiędzy niekolejnymi przystankami A i B, to musimy dodać czasy przejazdów między kolejnymi parami przystanków na trasie między A i B (w całym zadaniu zakładamy, że czas postoju tramwaju na przystanku jest zerowy oraz czasy przejazdów pomiędzy tymi samymi przystankami są zawsze takie same).
Z drugiej strony, czasy przejazdów zwykle nie są pełnymi minutami. Wówczas dodając wartości z tabliczki (które są w jakiś sposób zaokrąglone do pełnych minut) dodajemy wartości obarczone pewnym błędem, który się może kumulować. Tabliczkę oceniamy patrząc na maksymalny błąd spośród błędów jakie popełniamy wyliczając czasy przejazdów między wszystkimi parami (nie koniecznie kolejnymi) przystanków. Błąd między konkretną parą przystanków to wartość bezwzględna z różnicy między rzeczywistym czasem przejazdu tramwaju między nimi, a czasem uzyskanym z obliczeń na podstawie tabliczki. Dobrze zaprojektowana tabliczka minimalizuje tenże maksymalny błąd.

Zadanie

Napisz program, który dla podanych dokładnych czasów przejazdu między kolejnymi przystankami stwierdzi, jaki jest maksymalny błąd popełniany przy użyciu najlepiej zaprojektowanej tabliczki.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. Opis pojedynczego zestawu jest następujący. W pierwszej linii znajdują się dwie liczby całkowite - liczba przystanków N (1 ≤ N ≤ 10.000) oraz liczba jednostek pomiarowych M, na które jest podzielona jedna minuta (1 ≤ M ≤ 10.000). W następnych N–1 wierszach są podane dokładne czasy przejazdu pomiędzy kolejnymi przystankami, przedstawione za pomocą dwóch liczb całkowitych A i B (1 ≤ A ≤ 10.000, 0 ≤ B < M). Pierwsza z nich (A) określa liczbę minut, a druga (B) liczbę jednostek pomiarowych (jedna minuta = M jednostek pomiarowych).

Specyfikacja wyjścia

Każdemu zestawowi na wejściu powinna odpowiadać jedna linia na wyjściu. Ta linia powinna zawierać liczbę całkowitą określającą maksymalny błąd w najlepszej tabliczce, mierzony w jednostkach pomiarowych.

Przykład

3
4 60
1 20
2 30
4 10
3 100
1 50
1 50
3 100
0 10
0 20

30
50
30