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
W jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita
równa minimalnej możliwie sumie współczynników wrażeń kolejnych odcinków na trasie
wycieczki Bajtazara.
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.