Case

În cartierul matematicienilor, sunt exact $n$ case, așezate în linie. Fiecare casă are asociate:

• un număr (natural mai mare sau egal cu $0$);
• o valoare de risc, care este egală cu suma divizorilor numărului acelei case, fără el însuși.

Se consideră că o casă este perfectă dacă numărul său este strict mai mare decât $1$ și strict mai mare decât valoarea sa. O casă poate fi cumpărată cu o sumă de bani egală cu numărul casei respective.

De exemplu, casa cu numărul $10$ este perfectă deoarece numărul său este strict mare decât valoarea sa (numărul său este $10$ iar valoarea sa este egală cu suma divizorilor săi diferiți de numărul însuși: $1+2+5=8$).

Două case pot avea același număr. Numerele caselor sunt date într-o ordine oarecare.

Investitor bun, Micul Gates dorește să cumpere un număr maxim de case perfecte, fără ca suma plătită să depășească valoarea $S$ pe care o are la dispoziție. Dacă are la dispoziție mai multe variante, va alege secvența de case pentru care plătește cât mai puțin. De asemenea, pentru a eficientiza costurile de întreținere pentru casele cumpărate, el va alege doar o secvență de case vecine între ele.

Cerințe

1. Câte case perfecte sunt în cartierul matematicienilor?
2. Câte case cumpără Micul Gates și care este suma cheltuită de acesta?

Date de intrare

Pe prima linie a fișierului de intrare case.in se găsește un număr $c$ al cerinței, care poate fi doar $1$ sau $2$.
Pe a doua linie se găsesc $2$ numere naturale nenule, separate prin câte un spațiu, $n$ și $S$ ($n$ numărul de case, $S$ suma de bani pe care o are la dispoziție pentru a cumpăra case).
Pe a treia linie se găsesc $n$ numere naturale reprezentând numerele caselor din cartier în ordinea în care sunt așezate acestea.

Date de ieșire

Pe prima linie a fișierului de ieșire case.out se va găsi fie răspunsul la cerința $1$, fie răspunsul la cerința $2$.

Restricții și precizări

• $0 \leq \text{numărul unei case} \leq 10 \ 000$;
• $1 \leq n \leq 1 \ 000 \ 000$;
• $1 \leq S \leq 10 \ 000 \ 000 \ 000$;
• Pentru $48$ de puncte, cerința este $1$. Pentru $25$ de puncte, $n \leq 100$;
• Pentru $52$ de puncte, cerința este $2$.

Exemplul 1

case.in

1
9 10
6 15 7 4 4 4 4 5 14

case.out

8

Explicație

Cerința este $1$.
Casele perfecte sunt cele cu numerele: $15$, $7$, $4$, $4$, $4$, $4$, $5$, $14$.

Exemplul 2

case.in

2
9 13
6 6 7 4 4 4 4 2 12

case.out

3 10

Explicație

Cerința este $2$.
Cea mai lungă secvențe de case perfecte și pe care Micul Gates plătește cât mai puțin (maxim $13$) este formată din casele cu numerele: $4$, $4$, $2$.
Suma plătită este $10$.