판이 기울지 않게

지렛대 위에 물체를 올려놓으면, 물체는 받침점을 중심으로 지렛대를 회전시키려는 힘을 만든다. 이 회전력을 토크라고 하며, 그 크기는 물체의 무게에 받침점으로부터의 거리를 곱한 값이다. 물체가 받침점의 왼쪽에 있으면 토크의 방향은 반시계 방향이고, 오른쪽에 있으면 시계 방향이다. 어떤 받침점을 기준으로 한 전체 토크는 지렛대 위에 놓인 모든 물체의 토크를 합한 값이다(널빤지 자신도 그 무게가 중심에 작용하는 하나의 물체로 센다).

굵기와 무게가 고르게 분포된 곧은 널빤지가 있다. 널빤지의 한가운데가 무게중심이며, 그 위치를 0이라고 한다. 따라서 길이가 $L$인 널빤지의 양 끝은 각각 위치 $-L/2$와 $+L/2$이다. 널빤지는 위치 $-1.5$와 $+1.5$에 있는 똑같은 두 받침점 위에 놓여 있다. 널빤지 위에는 여러 개의 짐이 놓여 있고, 각 짐은 정수 위치(가운데에서 잰 거리이며 음수는 왼쪽)와 정수 무게로 주어진다.

짐을 한 번에 하나씩 치운다. 이때 널빤지가 절대로 기울어서는 안 된다. 널빤지는 (짐들과 널빤지 자신의 무게로 인한) 왼쪽 받침점 기준 전체 토크가 반시계 방향이거나, 오른쪽 받침점 기준 전체 토크가 시계 방향일 때 기운다. 어떤 받침점에서 전체 토크가 정확히 0으로 균형을 이루면 기울지 않는 것으로 본다. 처음 배치 상태에서도, 그리고 짐을 하나 치울 때마다도 항상 균형이 유지되어야 한다(짐이 하나도 없는 널빤지는 언제나 균형을 이룬다).

예를 들어 무게가 3kg이고 길이가 20m인 널빤지가 두 받침점 위에 놓여 있고, 위치 $-8, -4, -3, 2, 5, 8$에 각각 무게 $4, 10, 10, 4, 7, 8$kg인 여섯 개의 짐이 놓여 있다고 하자.

이 배치에서는 널빤지가 기울지 않도록 짐을 치우는 순서가 여러 가지 존재한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 정수로 시작한다: 널빤지의 길이(미터 단위, 3 이상), 널빤지의 무게(킬로그램 단위), 그리고 짐의 개수 $n$ ($n \le 20$). 널빤지는 항상 위치 $-1.5$와 $+1.5$에 있는 똑같은 두 받침점 위에 놓여 있다. 이어지는 $n$개의 줄에는 각각 두 정수, 즉 짐의 위치(가운데에서 잰 거리이며 음수는 왼쪽)와 무게(킬로그램)가 주어진다. 입력의 끝은 세 개의 0이 적힌 줄로 표시되며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 Case X: C 형식으로 한 줄을 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이고, C는 널빤지가 매 순간 기울지 않도록 짐을 한 번에 하나씩 모두 치울 수 있는 서로 다른 순서의 개수이다. 서로 다른 입력 줄에 주어진 짐은 위치와 무게가 같더라도 서로 다른 것으로 센다. 짐을 모두 치우는 것이 불가능하면(특히 처음 배치에서 이미 널빤지가 기울어 있으면) C로 0을 출력한다.