Wycieczka

Limit pamięci: 128 MB

Tegoroczna Bajtocka Olimpiada Informatyczna była wyjątkowo niepomyślna dla Bajtazara. Jako że nie zakwalifikował się on nawet do ostatniego etapu olimpiady, nie może wziąć udziału w Obozie Naukowo-Treningowym im. Bajtoniego Bitrara (ONTBB).

Czas, który minął od pamiętnych zawodów do wakacji, uleczył rany Bajtazara, lecz nie zaplanował mu żadnej wakacyjnej alternatywy. Na szczęście Bajtazar wziął sprawy w swoje ręce i postanowił udać się na wycieczkę rowerową po całej Bajtocji. Młody adept informatyki ustalił kolejnych miast, przez które ma przechodzić trasa jego wycieczki, a także dokładnie wybrał drogi, którymi będzie jechał do kolejnych miast. Każda z dróg ma swoją długość w kilometrach i współczynnik wrażeń, który może być zarówno dodatni jak i ujemny. Ostatnią rzeczą, którą należy zaplanować, jest podział całej trasy na odcinki odpowiadające kolejnym dniom jego wycieczki. Każdy odcinek ma się zaczynać i kończyć w pewnym mieście, a jego długość nie może przekraczać kilometrów. Ponadto, współczynnik wrażeń danego odcinka definiujemy jako kwadrat sumy współczynników wrażeń kolejnych dróg na tym odcinku. Bardziej formalnie, jeśli na dany odcinek składają się drogi o współczynnikach wrażeń kolejno , to współczynnikiem wrażeń tego odcinka jest liczba .

Ponieważ Bajtazar jest człowiekiem, którego przesadnie wielkie wrażenia przerażają, chciałby podzielić trasę na odcinki tak, aby żaden z nich nie był dłuższy niż kilometrów, a suma współczynników wrażeń kolejnych odcinków była jak najmniejsza. Pomóż mu w tym zadaniu.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i , () oznaczające odpowiednio liczbę dróg na trasie Bajtazara i maksymalną dopuszczalną długość odcinka. W następnych wierszach znajdują się opisy kolejnych dróg, -ty z tych wierszy zawiera dwie liczby całkowite i , () oznaczające odpowiednio długość w kilometrach i współczynnik wrażeń -tej drogi.

Wyjście

Przykład

Dla danych wejściowych:

5 15
7 4
8 -5
4 2
1 -1
2 4

poprawną odpowiedzią jest:

14

Autor zadania: Adam Karczmarz.