In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
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.
Dla danych wejściowych:
5 15 7 4 8 -5 4 2 1 -1 2 4
poprawną odpowiedzią jest:
14
Autor zadania: Adam Karczmarz.