마지막 일격

Diana가 가장 좋아하는 게임을 플레이하면서 얻는 골드를 최대화할 수 있도록 도와주어야 한다. Diana는 종종 자신의 타워 가까이에 서서 N마리의 몬스터와 마주하는 상황에 놓인다. 이때 Diana와 타워는 번갈아 몬스터를 공격하며, Diana가 먼저 공격한다. Diana의 차례에는 공격할 몬스터를 선택할 수 있다(즉, Diana는 자신의 차례를 건너뛸 수 있다). 타워의 차례에는 타워에서 가장 가까운 몬스터를 공격한다. Diana와 타워는 죽은 몬스터를 공격할 수 없다.

Diana가 몬스터를 공격하면 그 몬스터의 체력이 P만큼 감소한다. 타워가 몬스터를 공격하면 그 몬스터의 체력이 Q만큼 감소한다. 몬스터의 체력이 1 미만으로 감소하면 몬스터가 죽는다. i^{th} 몬스터의 초기 체력은 $H_{i}$이다. Diana의 공격으로 i^{th} 몬스터를 죽이면 Diana는 $G_{i}$ 골드를 받지만, 타워의 공격으로 죽이면 골드를 받지 못한다. Diana가 얻을 수 있는 골드의 최대량은 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100 20 ≤ P ≤ 200 20 ≤ Q ≤ 200 1 ≤ $H_{i}$ ≤ 200 0 ≤ $G_{i}$ ≤ $10^{6}$

작은 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 4

큰 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 100

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 P, Q, N을 나타내는 공백으로 구분된 세 정수가 포함된 한 줄로 시작한다. 이어서 N개의 줄이 주어지며, i^{th} 줄에는 $H_{i}$와 $G_{i}$를 나타내는 공백으로 구분된 두 정수가 주어진다.

몬스터들은 타워에서 가까운 순서대로 주어진다. 다시 말해, 타워는 모든 몬스터 < i가 죽은 경우에만 i^{th} 몬스터를 공격한다.

각 테스트 케이스마다 "Case #x: y"가 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Diana가 얻을 수 있는 골드의 최대량이다.

두 번째 예제에서 Diana는 첫 번째 몬스터를 포기해야 한다. 자신의 첫 두 차례 동안 세 번째 몬스터를 미리 공격하여 체력을 80까지 낮추면, 두 번째와 세 번째 몬스터에게 쉽게 마지막 일격을 가할 수 있다.