가로수 버팀목 (Large)
시간 제한5초메모리 제한512 MB
막대 하나나 두 개를 묶어 모든 나무가 지지력 B를 만족하도록 배치하고 사용한 지지력 합을 최소로 구합니다.
문제
당신은 G 시의 시장으로 당선되었다. 도시 미화 사업으로 길가에 가로수를 심기로 했다. 그런데 나무를 사들인 뒤에야 나무가 곧게 자라려면 버팀목이 필요하다는 사실을 알았다.
지금 가지고 있는 나무막대기만으로 사들인 가로수를 전부 받칠 수 있는지 알고 싶다. 조건은 다음과 같다.
- 나무를 하나도 빠뜨리지 않고 모두 지지해야 한다.
- 나무 하나를 지지하는 데 필요한 지지력은 이고, 모든 나무가 같다.
- 나무를 지지하려면 나무막대기를 버팀목으로 세워야 하며, 세운 나무막대기의 지지력이 이상이어야 한다.
- 나무막대기는 지지력이 같은 것끼리 한 종류로 묶어 두었고, 종류마다 개수를 알고 있다.
- 미관 때문에 한 나무에는 버팀목을 최대 두 개까지만 세울 수 있다. 두 개를 세우면 두 막대기의 지지력을 합한 힘으로 나무를 지탱하므로, 그 합이 이상이면 된다.
- 나무막대기 하나는 나무 하나에만 쓸 수 있고, 쓰지 않고 남겨도 된다.
- 위 조건을 모두 지키는 방법 중에서 사용한 나무막대기의 지지력 합을 최소로 하라.
입력
변수를 다음과 같이 정의한다.
- = 테스트 케이스의 수
- = 나무의 개수
- = 나무 하나가 필요로 하는 지지력 (모든 나무가 같다)
- = 나무막대기 종류의 수
- = 번째 종류의 나무막대기 하나가 내는 지지력
- = 번째 종류의 나무막대기 개수
입력은 다음 형식으로 주어진다.
T
N M B
p1 q1
p2 q2
...
pM qM
첫 줄에 가 주어진다. 이어서 테스트 케이스가 개 주어진다. 각 테스트 케이스의 첫 줄에는 , , 가 공백으로 구분되어 주어지고, 다음 개 줄에 와 가 한 줄에 하나씩 주어진다.
제한
- 모든 입력은 정수이다.
출력
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이다. 가로수를 모두 지지할 수 있으면 에 사용한 나무막대기의 지지력 총합의 최솟값을 출력하고, 지지할 수 없으면 에 -1을 출력한다.