Cerință
Andrei tocmai și-a achiziționat noua mașină electrică albastră și acum dorește să se bucure de o plimbare. El și-a stabilit un traseu foarte lung însă și-a dat seama că este posibil să nu îl poată parcurge în întregime întrucât stațiile de încărcare nu sunt suficient de dese. Traseul ales este liniar, fără a se autointersecta.
Pentru fiecare stație se cunoaște distanța la care ea este amplasată față de locul de pornire.
Se mai cunoaște că Andrei pornește cu bateria încărcată la maxim și că în orice stație poate încărca oricât (evident, fără a depăși capacitatea bateriei).
Pentru ușurință vom considera capacitatea bateriei exprimată în număr de unități de distanță ce pot fi parcurse. Dacă bateria se termină înainte de a se ajunge într-o stație, mașina nu va mai putea ajunge în stație, dar dacă se termină exact în momentul ajungerii în stație, ea poate fi încărcată acolo.
Să se determine distanța maximă pe care Andrei o poate parcurge. De asemenea, se cere sa determinăm numărul minim de opriri pentru a atinge această distanță maximă.
Date de intrare
Fișierul electric.in conține pe prima linie un număr natural reprezentând capacitatea bateriei. Pe linia a doua este o valoare reprezentând numărul de stații de benzină aflate pe traseul lui Andrei. Pe linia a treia se află numere naturale, separate prin spații, reprezentând, pentru fiecare stație, distanța față de locul de pornire al lui Andrei.
Date de ieșire
Fișierul electric.out conține două valori, separate prin spațiu, reprezentând respectiv distanța maximă percursă de Andrei și numărul minim de opriri pentru a parcurge această distanță.
Restricții și precizări
- ;
- ;
- Distanțele până la stații sunt numere naturale nenule cel mult egale cu .
Exemplu
electric.in
3
4
4 2 7 11
electric.out
10 3
Explicație
Andrei are barerie de capacitate . El poate ajunge la stația aflată la distanța cu capacitate în baterie, acolo poate încarca bateria și mai consumă încă până la stația cu capacitate , la care ajunge tot cu în baterie. Acolo încarcă și ajunge cu în baterie la stația aflată la distanța . De acolo mai poate merge unități dar nu va mai ajunge la stația cu distanța pentru a mai putea încărca acolo.