YouTube

시간 제한1초메모리 제한1024 MB

요약

가치 1 또는 2인 영상들의 길이가 주어질 때, 총 가치가 V 이상이 되도록 최소 시청 시간을 구한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

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:

Kitų žaidėjų šachmatų partijų įrašus. Šių filmukų vertė yra $v\_i = 1$ .
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\\}$

예제2

예제 1
입력
```
4 3
1 4
1 5
2 7
2 4
```
예상 출력
```
8
```
예제 2
입력
```
3 42
2 3
1 4
1 1
```
예상 출력
```
-1
```