Konduktor
Limit pamięci: 32 MB
Bajtazar pracuje jako konduktor w ekspresie Bajtockich Kolei Państwowych (BKP) relacji
Bajtogród-Bitowice.
Rozpoczął się trzeci etap reformy BKP
(Historia reform BKP i stacji Bitowice została opisana w zadaniach
Koleje
z III etapu XIV OI oraz
Stacja
z III etapu XV OI.
Znajomość tych zadań nie jest jednak w najmniejszym stopniu potrzebna do rozwiązania niniejszego zadania.),
w ramach którego zmieniany jest system wynagrodzeń tak, aby lepiej motywował pracowników do efektywnej pracy.
Wynagrodzenie Bajtazara będzie teraz zależało od liczby sprawdzonych przez niego biletów
(pasażerów).
Bajtazar jest w stanie sprawdzić bilety wszystkich pasażerów w trakcie przejazdu między dwiema kolejnymi stacjami.
Nie ma jednak ani siły, ani chęci, żeby sprawdzać bilety między każdymi dwiema kolejnymi stacjami.
Po namyśle zdecydował się, że będzie sprawdzał bilety razy na trasie pociągu.
Przed wyruszeniem w trasę Bajtazar otrzymuje zbiorcze zestawienie, ilu pasażerów będzie jechało
z danej stacji do danej innej stacji.
Na podstawie tych danych Bajtazar chciałby tak dobrać momenty kontroli biletów, aby sprawdzić jak najwięcej
biletów.
Niestety, powtórne sprawdzenie biletu pasażera, który już raz został skontrolowany, nie wpływa na wynagrodzenie Bajtazara.
Napisz program, który pomoże ustalić Bajtazarowi, kiedy powinien kontrolować bilety, aby jego
zarobki były jak największe.
Wejście
W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite i
(, ), oddzielone pojedynczym odstępem i oznaczające liczbę stacji
na trasie pociągu oraz liczbę kontroli biletów, które chce przeprowadzić Bajtazar.
Stacje są ponumerowane kolejno od do .
W kolejnych wierszach jest zapisane zbiorcze zestawienie pasażerów.
Wiersz -szy zawiera informacje o pasażerach, którzy wsiądą na stacji -
jest to ciąg nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami:
.
Liczba (dla ) oznacza liczbę pasażerów, którzy wsiedli na stacji i jadą do stacji .
Łączna liczba pasażerów (czyli suma wszystkich ) wynosi nie
więcej niż .
Wyjście
Twój program powinien wypisać na standardowe wyjście (w jednym wierszu) rosnący ciąg liczb całkowitych
z przedziału od do , pooddzielanych pojedynczymi odstępami.
Liczby te mają być numerami stacji, po ruszeniu z których Bajtazar powinien sprawdzić bilety pasażerów.
Przykład
Dla danych wejściowych:
7 2
2 1 8 2 1 0
3 5 1 0 1
3 1 2 2
3 5 6
3 2
1
poprawną odpowiedzią jest:
2 5
lub
3 5
W obu przypadkach Bajtazar skontroluje 42 bilety.
Autor zadania: Marcin Kubica.