YouTube

문제

Rimantas mokosi žaisti šachmatais žiūrėdamas „YouTube“ filmukus. Kiekvienas filmukas turi tam tikrą mokamąją vertę, kuri priklauso nuo filmuko rūšies $r_{i}r\_i$. Paprastai Rimantas žiūri dviejų rūšių filmukus:

1. Kitų žaidėjų šachmatų partijų įrašus. Šių filmukų vertė yra $v_i=1v\_i\; =\; 1$.
2. Pamokas, kuriose paaiškinamos įvairios taktikos ir strategijos. Šių filmukų vertė yra dvigubai didesnė, t. y. $v_i=2v\_i\; =\; 2$.

Žinomi visi filmukai, kuriuos Rimantas gali peržiūrėti: jų trukmė ir rūšis (aprašyta aukščiau). Raskite, kiek mažiausiai laiko Rimtantas turės žiūrėti „YouTube“, kad surinktų bent $VV$ vertės taškų, jeigu:

• Rimantas nežiūri to paties filmuko kelis kartus (papildomos vertės tai neprideda).
• Pradėjęs filmuką, Rimantas visuomet jį peržiūri iki galo.

입력

Pirmojoje eilutėje įrašytas galimų filmukų skaičius $NN$ bei Rimanto norima pasiekti vertė $VV$. Kitose eilutėse pateikta po du sveikuosius skaičius apibūdinančius kiekvieną filmuką: filmuko rūšis $r_{i}r\_i$ bei trukmė $t_{i}t\_i$.

출력

Išveskite, kiek mažiausiai laiko Rimantas turės žiūrėti „YouTube“, kad surinktų bent $VV$ vertės taškų.

Jei surinkti tiek vertės taškų neįmanoma, išveskite $-1-1$.

4 3
1 4
1 5
2 7
2 4

8

3 42
2 3
1 4
1 1

-1