Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Scara

Adăugată de :
sorynsoo
Sursă :
OJI2005
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
1024 kbytes

Domnul G are de urcat o scară cu n trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe k dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta x. Dacă bea toată apa dintr-o astfel de sticlă, forţa şi mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la x trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conţinută de aceste sticle poate să difere de la o treaptă la alta.

Pe j trepte se află câte o sticlă cu băutura energizantă. Şi pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem y decilitri de băutură energizantă. Dacă bea q (q£y)  decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la 2q trepte, după care şi în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de q decilitri consumaţi, G trebuie să plătească q lei grei.

Pot exista trepte pe care nu se află nici un pahar, dar şi trepte pe care se află atât o sticlă cu apă cât şi una cu băutură energizantă. În astfel de situaţii, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.

 

Cerinţă

Determinaţi p, numărul minim de paşi pe care trebuie să îi facă G pentru a urca scara, precum şi suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în p paşi.

 

Date de intrare

Fişierul text de intrare  conţine:

  • pe prima linie un număr natural n, reprezentând numărul total de trepte;
  • pe cea de a doua linie un număr natural k,  reprezentând numărul de trepte pe care se află sticle cu apă;
  • pe fiecare dintre următoarele k linii câte două numere naturale separate printr-un spaţiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu apă şi respectiv cantitatea de apă din acea sticlă exprimată în decilitri;
  • pe următoarea linie un număr natural j, reprezentând numărul de trepte pe care se află sticle cu băutură energizantă;
  • pe fiecare dintre următoarele j linii câte două numere naturale separate printr-un spaţiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu băutură energizantă şi respectiv cantitatea de băutură energizantă din acea sticlă exprimată în decilitri.

 

Date de ieşire

Fişierul text de ieşire va conţine o singură linie pe care vor fi scrise două numere naturale p c separate printr-un spaţiu, p reprezentând numărul minim de paşi, iar c suma minimă cheltuită.

 

Restricţii

n <= 120

0 <= k <= n

0 <= j <= n

Cantitatea de apă aflată în oricare sticlă este 1 £ x £ 100

Cantitatea de băutură energizantă aflată în oricare sticlă este 1 £ y £ 100

 

Exemple

  Date de intrare

  Date de iesire

  Date de intrare

  Date de iesire

  6

  1

  1 2

  2 

  4 1

  1 2

  3 2  

  6

  1 

  1 2

  2

  4 1

  1 1

  4 1


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Grafuri


Comentarii

Adauga un comentariu: Click !