* $1 ≤ N ≤ 100 000$
* $1 ≤ M, P{~i~} ≤ 2 000 000 000$
* $1 ≤ K, L ≤ 2^60^$

* Pot exista doi alergatori cu aceeasi pozitie de start

* Pozitiile de start si vitezele cu care alearga participantii la competitie sunt numere naturale
* Un sir de viteze {$(X{~1~},X{~2~}...X{~N~})$} este mai mic din punct de vedere lexicografic decat un alt sir {$(Y{~1~},Y{~2~}...Y{~N~})$} daca exista o pozitie $p$ astfel incat {$X{~p~} < Y{~p~}$} si {$X{~1~} = Y{~1~}$}, {$X{~2~} = Y{~2~}$} ... {$X{~p-1~} = Y{~p-1~}$}

table(example). |_. progresii.in |_. progresii.out |
| 3 3 8 4
  1

  2

  2

  3
| 1
  1

h3. Explicatie

Sunt $3$ alergatori care pot bea cel mult $8$ decilitri de suc. Viteza unui alergator poate fi de maxim $3$ metri/secunda, iar pista masoara $4$ metri lungime. Primii doi concurenti vor alerga cu $1$ metru pe secunda, in timp ce ultimul va alerga cu $2$ metri/secunda. Primul concurent va bea un decilitru de suc in dreptul pozitiilor {$1$}, {$2$}, {$3$} si {$4$}, dupa care isi termina cursa. Concurentul al doilea va bea cate un decilitru in dreptul pozitiilor {$2$}, $3$ si {$4$}. Ultimul concurent va bea un singur decilitru de suc in dreptul pozitiei $3$, la momentul 0, deoarece in secunda urmatoare el va termina cursa (se va afla la distanta $5$ de capatul din stanga al pistei, care are lungimea {$4$}). In total s-au baut 8 decilitri de suc.

Sunt $3$ alergatori care pot bea cel mult $8$ decilitri de suc. Viteza maxima a unui alergator poate fi de $3$ metri/secunda, iar pista masoara $4$ metri lungime. Primii doi concurenti vor alerga cu $1$ metru pe secunda, in timp ce ultimul va alerga cu $2$ metri/secunda. Primul concurent va bea un decilitru de suc in dreptul pozitiilor {$1$}, {$2$}, {$3$} si {$4$}, dupa care isi termina cursa. Concurentul al doilea va bea cate un decilitru in dreptul pozitiilor {$2$}, $3$ si {$4$}. Ultimul concurent va bea un singur decilitru de suc in dreptul pozitiei $3$, la momentul 0, deoarece in secunda urmatoare el va termina cursa (se va afla la distanta $5$ de capatul din stanga al pistei, care are lungimea {$4$}). In total s-au baut 8 decilitri de suc.

O alta solutie ar fi fost ({$1, 1, 3$}), dar aceasta este mai mare din punct de vedere lexicografic.
== include(page="template/taskfooter" task_id="progresii") ==

2922