Klocki reaktywacja

Limit pamięci: 32 MB

Bajtazar bez żadnego problemu opanował sztukę układania klocków na prostokątnej planszy. Postanowił stawić czoła większemu wyzwaniu. Zastnanawia się na ile sposobów można klocków ułożyć w -wymiarową kostkę o boku , tak by suma numerów klocków w każdej -wymiarowej hiperpłaszczyźnie była liczbą pierwszą. Pokazał tę sztuczkę Bajtolinie, jednak nie wydawała się nią zainteresowana.

Mimo to, Bajtazar nie poddawał się. Dzięki wyjątkowym zdolnościom w układaniu klocków Bajtazar szybko wspinał się po kolejnych szczeblach kariery. Znalazł pracę w Ministerstwie Infrastruktury. Jego zadaniem jest optymalizacja pracy robotników budowlanych. Obecnie zajmuje się naprawą autostrady A1. Rozdział pracy wygląda następująco: autostradę dzieli się na odcinki długości kilometrów. Jeśli pierwszy odcinek zaczyna się na -tym kilometrze¹, to -ty z nich zaczyna się na kilometrze . Dla każdego kilometra autostrady wiemy czy wymaga on naprawy. Ekipy robotników należy wysłać na każdy -kilometrowy odcinek, w którym trzeba wyremontować co najmniej jeden kilometr. Zadaniem Bajtazara jest znalezienie takiego podziału autostrady na odcinki, by liczba odcinków na które zostaną wysłane załogi budowlane była jak najmniejsza. Pierwszy odcinek podziału musi się zaczynać na jednym z pierwszych kilometrów. Dodatkowo wiemy, że żaden spośród pierwszych kilometrów autostrady nie wymaga naprawy.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis uszkodzeń autostrady,
• wyznaczy podziały autostrady na odcinki minimalizujące wymaganą ilość ekip budowlanych,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite i () - długość pojedynczego odcinka oraz ilość uszkodzonych kilometrów. Druga linia zawiera rosnący ciąg liczb całkowitych () poodzielanych pojedynczymi spacjami. Każda z nich oznacza jeden kilometr autostrady, który wymaga naprawy.

Wyjście

W pierwym wierszu należy wypisać minimalną ilość wysłanych ekip remontowych. Druga linia powinna zawierać wszystkie możliwe kilometry, na których może rozpoczynać się pierwszy odcinek podziału, wypisane w kolejności rosnącej.

Przykład

Dla danych wejściowych:

4 3
7 14 15

poprawną odpowiedzią jest:

2
1 2 4

Zapożyczenie z chorwackiej olimpiady informatycznej: Jakub Łącki.