30059번 - 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$. Paprastai Rimantas žiūri dviejų rūšių filmukus:

1. Kitų žaidėjų šachmatų partijų įrašus. Šių filmukų vertė yra $v_i = 1$.
2. Pamokas, kuriose paaiškinamos įvairios taktikos ir strategijos. Šių filmukų vertė yra dvigubai didesnė, t. y. $v_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 $V$ 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 $N$ bei Rimanto norima pasiekti vertė $V$. Kitose eilutėse pateikta po du sveikuosius skaičius apibūdinančius kiekvieną filmuką: filmuko rūšis $r_i$ bei trukmė $t_i$.

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

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

• $1 ≤ N ≤ 1\,000\,000$
• $1 ≤ V, t_i ≤ 1\,000\,000$
• $r_i ∈ \{1, 2\}$