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.