정육점

은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 원하는 무게만큼 고기를 살 수 있지만, 은혜가 방문한 정육점은 할인 행사 때문에 이미 잘라 둔 N개의 고기 덩어리만 판매한다.

각 덩어리에는 무게와 가격이 정해져 있다. 어떤 덩어리를 사면, 그 덩어리보다 가격이 싼 덩어리는 추가 비용 없이 원하는 만큼 덤으로 받을 수 있다. 단, 가격이 같은 덩어리는 덤으로 받을 수 없으므로 필요하다면 각각 구매해야 한다. 덩어리마다 부위가 다를 수 있어 가격이 무게에 비례하지 않을 수도 있다.

은혜는 부위를 고려하지 않고 필요한 총량 이상의 고기만 얻으면 된다. 더 싸다면 필요한 양보다 더 많은 고기를 얻어도 된다. 각 덩어리의 정보가 주어졌을 때, 필요한 양 이상의 고기를 얻기 위해 지불해야 하는 최소 비용을 구하라.

첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000)과 M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 고기 덩어리의 개수이고, M은 은혜에게 필요한 고기의 양이다.

다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 음이 아닌 두 정수가 주어진다. 모든 덩어리의 무게 합과 가격 합은 각각 2,147,483,647을 넘지 않는다.

첫째 줄에 필요한 최소 비용을 출력한다. 원하는 양을 얻을 수 없다면 -1을 출력한다.

무게가 4이고 가격이 8인 덩어리 하나를 사면, 가격이 더 싼 나머지 덩어리를 모두 덤으로 받을 수 있다. 이때 얻는 고기의 총무게는 10kg이므로 필요한 9kg 이상이 된다.