12415번 - 가로수 (Small)

당신은 G 시의 시장으로 당선되었다. 도시미화의 일부분으로서, 당신은 길가에 가로수를 심기로 하였다. 그런데 나무를 사들인 다음에야, 나무가 건강하게 자라기까지 필요한 버팀목이 필요하다는 사실을 깨달았다.

이런 상황에서, 가지고 있는 나무막대기만 이용해서 사들인 모든 가로수에 효율적으로 버팀목을 대는 것이 가능한지 알고 싶다. 여기 자세한 제약 조건이 있다.

• 모든 나무를 빠짐없이 지지해야 한다.
• 각각의 나무에 필요한 지지력과 각 나무막대기가 제공할 수 있는 지지력을 모두 알고 있다.
  각각의 나무를 지지하는 데 필요한 지지력은 모두 같다.
• 한 나무를 지지하려면, 나무막대기를 버팀목으로 써야 한다. 이때, 사용된 나무막대기의 지지력이 나무가 필요로 하는 지지력 이상이어야 한다.
• 나무막대기는 같은 지지력을 줄 수 있는 것들을 묶어 한 종류로 구분해 두었고, 종류별 수량을 알고 있다.
• 도시미화로 하는 것이기 때문에, 버팀목은 한 나무당 최대 2개까지밖에 사용할 수 없다.
  두 개의 나무막대기를 사용할 경우, 두 나무 막대는 각각 지지력의 합만큼의 힘으로 나무를 지탱할 수 있다.
• 위의 조건을 다 만족하는 경우 중에, 사용된 나무막대기의 지지력의 합을 최소화시켜라.

다음과 같이 변수들을 정의하자.

• T = 테스트 케이스의 숫자
• N = 나무의 개수
• B = 각 나무가 필요로 하는 지지력. (모든 나무에 동일)
• M = 나무막대기의 종류
• p_i = i 번째 종류의 나무막대기들이 제공하는 지지력.
• q_i = i 번째 종류 나무막대기들의 개수.

   

이때, 입력은 다음과 같이 주어진다.

T
N M B
p1 q1
p2 q2
...
pM qM

제한

• 모든 입력은 정수로 주어진다.
• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 10
• 1 ≤ M ≤ 10
• 1 ≤ B ≤ 1000
• 1 ≤ p_i ≤ 2000
• 1 ≤ q_i ≤ 20

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이다. 만약, 모든 가로수를 심는 것이 가능하다면, 가로수를 지지하는데 사용된 막대기들의 지지력의 총 합 y을 출력하고, 불가능하다면 -1 를 대신 출력한다.