Fişierul intrare/ieşire:	cadouri.in, cadouri.out	Sursă	InfoPro, Etapa 3, Grupa B
Autor	Alexandru Petrescu	Adăugată de	Udristoiu Alexandra Maria •alexandra_udristoiu
Timp execuţie pe test	0.3 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Cadouri

Pentru că Lili a uitat să îi dea un cadou de Crăciun prietenei ei, Georgiana, s-a gândit să se revanşeze aducându-i cadouri timp de N zile. Astfel, în fiecare zi i din cele N, Lili va duce în faţa casei Georgianei cnt_i cadouri, toate de mărime m_i. După cele N zile, Georgiana se apucă să sorteze cutiile cu cadouri în ordine crescătoare după mărime. Deoarece s-au strâns foarte multe cadouri, Georgiana te roagă să afli mărimea celui de al K-lea cadou după sortare.

Date de intrare

Vă rugăm să consultaţi fişierul manager.cpp pe care îl puteţi găsi în ataşamente.

Date de ieşire

În fişierul de ieşire cadouri.out se va afişa un singur număr, mărimea celui de-al K-lea cadou în ordinea sortării.

Notă

Între ataşamente, puteţi găsi fişierul manager.cpp pe care îl puteţi descărca. E recomandat, atât pentru a scrie o sursa eficientă şi elegantă, cât şi pentru a simula experienţa problemei din timpul concursului, să completaţi această sursă cu implementarea funcţiei solve().

Restricţii

1 ≤ N ≤ 5 000 000
1 ≤ cnt_i, m_i ≤ 10⁹, pentru orice i de la 0 la N - 1
$1 \leq K \leq \sum_{i=0}^{N-1} cnt_i$
Pe testele oficiale, şirurile cnt şi m sunt generate pseudo-random. Detaliile sunt ascunse concurenţilor.
Testele sunt grupate pe subtaskuri. Punctele pe un subtask sunt acordate doar dacă sursa trece toate testele din respectivul subtask. Punctajele pe subtaskuri diferă de cele din concurs.
Subtask 1, în valoare de 15 puncte, $\sum_{i=0}^{N-1} cnt_i \leq 5\ 000\ 000$
Subtask 2, în valoare de 15 puncte, N ≤ 50 000
Subtask 3, în valoare de 15 puncte, K = 4
Subtask 4, în valoare de 30 puncte, 1 ≤ m_i ≤ 3, pentru orice i de la 0 la N - 1
Subtask 5, în valoare de 25 puncte, fără restricţii suplimentare