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

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

• 모든 나무를 빠짐없이 지지해야 한다.
• 각각의 나무에 필요한 지지력과 각 나무막대기가 제공할 수 있는 지지력을 모두 알고 있다.
  각각의 나무를 지지하는 데 필요한 지지력은 모두 같다.
• 한 나무를 지지하려면, 나무막대기를 버팀목으로 써야 한다. 이때, 사용된 나무막대기의 지지력이 나무가 필요로 하는 지지력 이상이어야 한다.
• 나무막대기는 같은 지지력을 줄 수 있는 것들을 묶어 한 종류로 구분해 두었고, 종류별 수량을 알고 있다.
• 도시미화로 하는 것이기 때문에, 버팀목은 한 나무당 최대 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 ≤ 100000
• 1 ≤ M ≤ 1000
• 1 ≤ B ≤ 10000
• 1 ≤ p_i ≤ 20000
• 1 ≤ q_i ≤ 200000

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

예제 입력

2
2 3 10
6 1
4 1
12 2
2 3 10
3 1
5 1
10 1

예제 출력

Case #1: 22
Case #2: -1