Electric

Time limit: 0.1s Memory limit: 64MB Input: electric.in Output: electric.out

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 CC reprezentând capacitatea bateriei. Pe linia a doua este o valoare nn reprezentând numărul de stații de benzină aflate pe traseul lui Andrei. Pe linia a treia se află nn 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

  • 1C1 000 000 0001 \leq C \leq 1 \ 000 \ 000 \ 000;
  • 1n100 0001 \leq n \leq 100 \ 000;
  • Distanțele până la stații sunt numere naturale nenule cel mult egale cu 1 000 000 0001 \ 000 \ 000 \ 000.

Exemplu

electric.in

3
4
4 2 7 11

electric.out

10 3

Explicație

Andrei are barerie de capacitate 33. El poate ajunge la stația aflată la distanța 22 cu capacitate 11 în baterie, acolo poate încarca bateria și mai consumă încă 22 până la stația cu capacitate 44, la care ajunge tot cu 11 în baterie. Acolo încarcă și ajunge cu 00 în baterie la stația aflată la distanța 77. De acolo mai poate merge 33 unități dar nu va mai ajunge la stația cu distanța 1111 pentru a mai putea încărca acolo.

Log in or sign up to be able to send submissions!