Rezolvare PBinfo #2860

Se dă un șir de n cifre. Șirul se împarte în secvențe disjuncte de cifre, fiecare secvență având lungimea cel mult 6. Cu fiecare secvență extrasă se formează numărul corespunzător și apoi se adună doar numerele prime obținute. De exemplu, dacă șirul de cifre este 37237, se pot extrage secvențele disjuncte 3, 72, 37, iar suma numerelor prime este 3 + 37 = 40. O altă modalitate este 3, 7237 care are suma 7240 (deoarece numărul 7237 este prim).

Cerința

Să se determine suma maximă care se poate obține împărțind șirul în secvențe disjuncte de lungimi cel mult 6 și adunând apoi numai numerele prime.

Date de intrare

Programul citește de la tastatură șirul de cifre, fără spații.

Date de ieșire

Programul va afișa pe ecran suma maximă obținută.

Restricții și precizări

• 1 ≤ lungimea șirului de cifre ≤ 100.000
• Dacă din șir nu se pot obține numere prime suma va fi 0.

Exemplul 1:

Intrare

37237

Ieșire

7240

Exemplul 2:

Intrare

44688

Ieșire

0

Exemplul 3:

Intrare

1234577

Ieșire

123464

Explicație

Numărul 1234577 este prim, dar nu poate fi luat ca o singură secvență deoarece are mai mult de 6 cifre. Suma maximă este 123457 + 7 = 123464.