YouTube

립만타스는 체스를 두면서 유튜브 동영상을 본다. 동영상마다 종류 $r_i$에 따라 정해진 가치가 있다. 립만타스가 보는 동영상은 보통 두 종류이다.

1. 다른 사람들이 둔 체스 대국 영상. 이 동영상의 가치는 $v_i = 1$이다.
2. 여러 전술과 전략을 설명하는 강의. 이 동영상의 가치는 $v_i = 2$로, 대국 영상의 두 배이다.

립만타스가 볼 수 있는 동영상은 모두 주어지며, 각 동영상의 길이 $t_i$와 종류 $r_i$를 알고 있다. 립만타스가 적어도 $V$ 이상의 가치를 얻으려면 유튜브를 최소 얼마나 오래 봐야 하는지 구한다. 조건은 다음과 같다.

• 같은 동영상을 여러 번 보지 않는다. 다시 봐도 가치가 추가되지 않는다.
• 동영상을 한 번 시작하면 끝까지 본다.

첫째 줄에 볼 수 있는 동영상의 개수 $N$과 립만타스가 얻고자 하는 가치 $V$가 주어진다. 다음 줄부터는 각 동영상의 종류 $r_i$와 길이 $t_i$를 나타내는 정수 두 개가 한 줄에 하나씩 주어진다.

립만타스가 적어도 $V$ 이상의 가치를 얻기 위해 유튜브를 봐야 하는 최소 시간을 출력한다. 그런 가치를 얻는 것이 불가능하면 $-1$을 출력한다.

$1 \le N \le 1\,000\,000$, $1 \le V, t_i \le 1\,000\,000$, $r_i \in \{1, 2\}$.