Se consideră un şir de biţi şi un număr natural K. Şirul se împarte în secvenţe astfel încât fiecare bit din şir să aparţină unei singure secvenţe şi fiecare secvenţă să aibă lungimea cel puţin 1 şi cel mult K. După împărţire, fiecare secvenţă de biţi se converteşte în baza 10, obţinându-se un şir de valori zecimale. De exemplu, pentru şirul de biţi 1001110111101010011 şi K = 4, se poate obţine 1 0011 101 111 0 1010 011, apoi în baza 10: 1, 3, 5, 7, 0, 10, 3. O altă împărţire poate fi 1 00 1 1 10 11 110 1010 011, adică 1, 0, 1, 1, 2, 3, 6, 10, 3.

Cerința

Scrieţi un program care:

• determină valoarea maximă (în baza 10) care se poate obţine dintr-o secvenţă de cel mult K biţi
• împarte şirul iniţial în secvenţe de cel mult K biţi astfel încât şirul zecimal obţinut să conţină un subşir strict crescător de lungime maximă posibilă.

Date de intrare

Fișierul de intrare blis.in conține pe prima linie numărul natural K, iar pe linia a doua se află şirul de biţi, şirul neconţinând spaţii.

Date de ieșire

Fișierul de ieșire blis.out va conține pe prima linie un număr natural reprezentând valoarea maximă care se poate obţine dintr-o secvenţă de cel mult K biţi, iar pe linia a doua un singur număr natural reprezentând lungimea maximă a subşirului strict crescător care se poate obţine din şirul de biţi prin împărţirea sa în secvenţe de cel mult K biţi.

Restricții și precizări

• 3 ≤ lungimea şirului de biţi ≤ 100 000
• pentru 70% din teste, lungimea şirului de biţi ≤ 1000
• 1 ≤ K ≤ 30
• Un subşir se obţine dintr-un şir prin eliminarea a zero, unul, două sau mai multe elemente;
• O secvenţă este formată din elemente aflate pe poziţii consecutive în şir;

Exemplu:

blis.in

4
1001110111101010011

blis.out

15
6

Explicație

Secvenţa de valoare maximă de cel mult 4 biţi este 1111, adică 15 în baza 10.
Pentru cerinţa a doua, şirul binar se împarte astfel:
1 00 1 1 10 11 110 1010 011,
Se obţine şirul zecimal:
1, 0, 1, 1, 2, 3, 6, 10, 3.
Subşirul strict crescător maximal de lungime 6 este 0, 1, 2, 3, 6, 10