가로수 버팀목 (Small)

당신은 G 시의 시장으로 당선되었다. 도시 미화 사업의 하나로 길가에 가로수를 심기로 했는데, 나무를 다 사들인 다음에야 나무가 건강하게 자라려면 버팀목이 필요하다는 사실을 깨달았다.

지금 가지고 있는 나무막대기만으로 사들인 가로수 전부에 버팀목을 댈 수 있는지 알고 싶다. 조건은 다음과 같다.

• 나무를 한 그루도 빠짐없이 지지해야 한다.
• 각 나무에 필요한 지지력과 각 나무막대기가 내는 지지력을 모두 알고 있다. 나무 한 그루를 지지하는 데 필요한 지지력은 $B$로 모두 같다.
• 나무를 지지하려면 나무막대기를 버팀목으로 써야 한다. 막대기를 하나만 쓸 때는 그 막대기의 지지력이 $B$ 이상이어야 한다.
• 나무막대기는 지지력이 같은 것끼리 묶어 종류로 구분해 두었고, 종류마다 개수를 알고 있다. 막대기 하나는 나무 한 그루에만 쓸 수 있다.
• 도시 미화 사업이므로 한 나무에 버팀목을 최대 2개까지만 쓸 수 있다. 막대기 두 개를 쓰면 두 지지력의 합만큼의 힘으로 나무를 지탱한다.

위 조건을 모두 만족하는 방법 중에서 사용한 나무막대기의 지지력 합을 최소로 하라.

다음과 같이 변수를 정의한다.

• $T$ = 테스트 케이스의 수
• $N$ = 나무의 개수
• $B$ = 나무 한 그루가 필요로 하는 지지력 (모든 나무에 동일하다)
• $M$ = 나무막대기의 종류 수
• $p_i$ = $i$번째 종류의 나무막대기가 내는 지지력
• $q_i$ = $i$번째 종류의 나무막대기 개수

첫 줄에 $T$가 주어지고, 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

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

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 모든 가로수에 버팀목을 댈 수 있으면 사용한 막대기의 지지력 합의 최솟값을 $y$ 자리에 출력하고, 불가능하면 $y$ 자리에 -1을 출력한다.