게이머 서연이는 캐릭터의 체력을 최소 \(V\) 이상으로 만들고 싶다. 상점에는 \(N\) 개의 물약이 있고, \(i\) 번째 물약은 비용 \(c_i\) 코인을 내면 체력을 정확히 \(h_i\) 만큼 올려 준다. 각 물약은 한 번씩만 살 수 있다.

물약들을 적절히 골라 체력 증가량의 합이 \(V\) 이상이 되도록 만들 때, 필요한 최소 비용을 구하여라. 어떤 방법으로도 체력을 \(V\) 이상으로 올릴 수 없다면 \(-1\) 을 출력한다.

• \(1 \le N \le 200\)
• \(1 \le V \le 30{,}000\)
• \(1 \le c_i \le 10{,}000\)
• \(1 \le h_i \le V\)

첫째 줄에 물약의 수 \(N\) 과 목표 체력 \(V\) 가 주어진다.

이어지는 \(N\) 개의 줄에 각각 물약의 비용 \(c_i\) 와 체력 증가량 \(h_i\) 가 주어진다.

최소 비용을 출력하고, 불가능하면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original