고대의 문
시간 제한1초메모리 제한512 MB
각 아이템을 몇 번 던질지 정한다. 던질 때마다 현재 공격력만큼 내구도를 깎고 공격력은 두 배, 가치는 절반이 되며, 피해 H 이상을 주면서 잃는 가치 합의 최솟값을 구한다.
문제
Pandy는 자신이 가장 좋아하는 게임인 "고대의 문"의 마지막 스테이지에 있다. 목표는 신성한 문을 통과하는 것이다. 방법은 두 가지다. 강력한 수호자를 물리치고 신성한 문의 열쇠를 빼앗거나, 신성한 문을 (무력으로) 직접 부수는 것이다.
Pandy는 강력한 수호자와 싸울 자신이 없어서 두 번째 방법을 택했다. Pandy에게는 신성한 문에 던질 수 있는 N개의 아이템이 있다. 각 아이템은 처음에 공격력 Pi와 가치 Vi를 가진다. Pandy가 i번째 아이템을 신성한 문에 던지면 다음이 순서대로 일어난다.
- 신성한 문의 내구도가 i번째 아이템의 현재 공격력만큼 감소한다.
- i번째 아이템의 공격력이 두 배가 된다.
- i번째 아이템의 가치가 반으로 줄어든다 (내림).
같은 아이템은 가치가 0이 되지 않는 한 신성한 문에 여러 번 던질 수 있다.
처음에 신성한 문의 내구도는 H이다. Pandy는 아이템을 하나 이상 던져 이 내구도를 0 이하로 만들어 신성한 문을 부숴야 한다.
불행히도 이 게임의 플레이어 점수는 게임이 끝났을 때 플레이어가 가진 모든 아이템의 가치 합으로 정해진다 (그래서 다른 플레이어들은 강력한 수호자와 싸우는 쪽을 선호한다). 그러므로 Pandy가 신성한 문을 부수면서 잃는 모든 아이템 가치 합의 최솟값을 구하도록 도와라.
예를 들어 H = 100, N = 3, P1..3 = {10, 75, 50}, V1..3 = {2, 10, 50}이라 하자.
신성한 문을 부수기 위해 Pandy는 두 번째 아이템을 두 번 던질 수 있다.
- 2번째 아이템을 던진다: H가 75만큼 감소하고, P2가 150으로 두 배가 되며, V2가 5로 반이 된다 (5만큼 손실).
- 2번째 아이템을 던진다: H가 150만큼 감소하고, P2가 300으로 두 배가 되며, V2가 2로 반이 된다 (3만큼 손실).
신성한 문에 가한 총 피해는 75 + 150 = 225로, 신성한 문을 부수기에 충분하다 (원래 H = 100). 모든 아이템 가치 합의 손실은 5 + 3 = 8이다.
또는 Pandy는 첫 번째 아이템을 두 번, 두 번째 아이템을 한 번 던질 수 있다.
- 1번째 아이템을 던진다: H가 10만큼 감소하고, P1이 20으로 두 배가 되며, V1이 1로 반이 된다 (1만큼 손실).
- 1번째 아이템을 던진다: H가 20만큼 감소하고, P1이 40으로 두 배가 되며, V1이 0으로 반이 된다 (1만큼 손실). 이 아이템은 더 이상 사용할 수 없다.
- 2번째 아이템을 던진다: H가 75만큼 감소하고, P2가 150으로 두 배가 되며, V2가 5로 반이 된다 (5만큼 손실).
신성한 문에 가한 총 피해는 10 + 20 + 75 = 105이고, 모든 아이템 가치 합의 손실은 1 + 1 + 5 = 7이다. 이 예에서 모든 아이템 가치 합의 손실을 7보다 작게 하면서 신성한 문을 부수는 방법은 없다.
입력
입력은 두 정수 N H (1 ≤ N ≤ 100; 1 ≤ H ≤ 10^9)를 포함하는 한 줄로 시작한다. 각각 사용할 수 있는 아이템의 수와 신성한 문의 처음 내구도이다. 다음 N개 줄은 각각 두 정수 Pi Vi (1 ≤ Pi ≤ 10^9; 1 ≤ Vi ≤ 100)를 포함한다. 각각 i번째 아이템의 처음 공격력과 가치이다.
출력
신성한 문을 부수면서 잃는 모든 아이템 가치 합의 최솟값을 한 줄에 출력한다. 신성한 문을 부수는 것이 불가능하면 -1을 출력한다.