Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-12-29 21:37:37.
Revizia anterioară Revizia următoare

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

Fişierul de intrare cadouri.in conţine pe prima linie 2 numere naturale N şi K, cu semnificaţia din enunţ. Următoarele N linii conţin câte 2 numere, cnt_i şi m_i, separate prin câte un spaţiu, reprezentând descrierea cadourilor din ziua i.

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.

Restricţii

1 ≤ N ≤ 5 000 000
1 ≤ cnt_i, m_i ≤ 10^9, pentru orice i de la 0 la N - 1
$1 \leq K \leq \sum_{i=0}^{N-1} cnt_i$
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