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

Vezi solutiile trimise | Statistici

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
• 
• 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,
• 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

Exemplu

Explicaţie

...

Cum se trimit solutii?