인쇄

신입생 맥스는 이제 공부에 본격적으로 뛰어들기로 했다. 내일 있을 신화학 세미나를 위해 그는 $k$쪽짜리 보고서를 준비해야 한다. 맥스는 신화학을 좋아하므로 보고서는 이미 다 썼고, 이제 인쇄만 하면 된다.

안타깝게도 기숙사에 있는 모든 프린터의 카트리지가 떨어져서, 맥스는 보고서를 인쇄하려고 새 카트리지를 사야 한다. 가게에는 $n$종류의 카트리지가 있었다. 점원은 맥스에게 카트리지에는 가격과 인쇄할 수 있는 페이지 수라는 두 가지 주요 파라미터가 있다고 설명했다.

$i$번째 종류의 카트리지는 $c_i$루블이고 $p_i$쪽을 인쇄할 수 있다. 가게에는 각 종류의 카트리지가 무제한으로 있다.

맥스는 가난한 학생이라 보고서를 인쇄하기에 합쳐서 충분한 선에서 카트리지를 최대한 싸게 사고 싶다. 한편 맥스는 매우 욕심이 많다. 보고서를 인쇄한 뒤에 한 쪽이라도 인쇄할 자원이 남으면, 앞으로 1년 동안 기숙사 사람들이 모두 그에게 문서를 인쇄하러 온다는 것을 그는 알고 있다.

그래서 맥스는 정확히 $k$쪽을 인쇄하기에 충분한 카트리지를 최소 총비용으로 사고 싶다.

맥스를 도와주자. 그가 지불해야 할 최소 금액을 구하라.

입력 파일의 첫 줄에는 가게의 카트리지 종류 수 $n$과 맥스의 보고서 쪽 수 $k$가 주어진다 ($1 \le n \le 100\,000$, $1 \le k \le 10^{9}$). 이어서 $n$개의 줄이 주어지고, 그중 $i$번째 줄에는 $i$번째 종류의 카트리지 가격 $c_i$와 그것으로 인쇄할 수 있는 쪽 수 $p_i$가 주어진다 ($1 \le c_i, p_i \le 200$).

출력 파일에는 정확히 $k$쪽을 인쇄하기 위해 맥스가 지불해야 할 최소 금액을 하나의 수로 출력한다. 해가 존재하지 않으면 출력 파일에 $-1$을 출력한다.

첫 번째 예에서 맥스는 두 번째 종류의 카트리지 하나와 네 번째 종류의 카트리지 두 개를 사야 한다. 4루블을 지불하면 맥스는 정확히 5쪽을 인쇄할 수 있다.

두 번째 예에는 카트리지 종류가 하나뿐이다. 이것을 사면 3쪽을 인쇄할 수 있는데, 이는 필요한 2쪽보다 많다.