문제

알코올 도수는 술에 들어 있는 에탄올의 비율이다. 예를 들어, 알코올 도수가 도인 맥주 ml에는 에탄올이 ml 들어 있다.

찬우는 에탄올을 ml 이상 섭취하면 취한다. 취하고 싶은 찬우 앞에는 술이 종류 있다. 번째 술은 도이며 한 병에 ml, 병당 가격은 원이다. 술은 병 단위로만 살 수 있으며, 모든 종류의 술은 충분히 많아서 찬우가 원하는 만큼 살 수 있다.

찬우는 술을 한 가지만 골라 취할 수 있을 만큼 구매할 것이다. 취하기 위해 필요한 최소 비용을 구하시오.

입력

첫째 줄에 술 종류의 개수 과 찬우의 주량 가 공백으로 구분되어 주어진다.

둘째 줄부터 줄에 걸쳐 각 술의 정보가 주어진다. 그중 번째 줄에는 번째 술의 알코올 도수 , 병당 용량 , 병당 가격 가 공백으로 구분되어 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

첫째 줄에 찬우가 취하기 위해 필요한 최소 비용을 출력한다.

아무리 많은 술을 구매해도 찬우가 취할 수 없다면 -1을 출력한다.

노트

첫 번째 예제에서, 첫 번째 술으로 취하려면 3병을 구매해야 한다. 두 번째 술은 40병, 세 번째 술은 3병, 네 번째 술은 18병, 다섯 번째 술은 2병을 구매하면 취할 수 있다. 가격을 고려하였을 때 다섯 번째 술을 2병 사는 것이 가장 싸니 답은 41800이다.

첫 번째 예제의 술은 모두 실존한다.