Untitled

Có N vị giám khảo trong kỳ thi chọn đội tuyển tin học. Kỳ thi bao gồm K bài. Vị giám khảo thứ i đề nghị số điểm của bài j là Aịj.

Hội đồng giám khảo muốn xác định số điểm cho mỗi bài sao cho:

Tổng số điểm bằng S.

Điểm của mỗi bài không bé hơn điểm của bài trước đó.

Số điểm của mỗi bài bằng điểm đề nghị cho bài này của một vị giám khảo nào đó.

 

Input

Dòng đầu tiên chứa số nguyên T là số testcase (T ≤ 100). Trong đó mỗi testcase sẽ chứa:

Dòng đầu chứa ba số nguyên S, K, N (1 ≤ S ≤ 200), (1 ≤ K ≤ 20), (1 ≤ N ≤ 20).

Dòng thứ i trong số N dòng tiếp theo chứa K số nguyên, số thứ j cho biết giá trị Aij là số điểm vị giám khảo thứ i đề nghị cho bài thứ j. (1 ≤ Aij ≤ 100),

 

Output

Kết quả của mỗi testcase sẽ được in theo định dạng sau:

Dòng đầu tiên là: “Case number_testcase”

Nếu tồn tại một cách cho điểm thỏa mãn yêu cầu in ra số trường hợp thỏa mãn.

Nếu không tồn tại cách cho điểm, in ra -1.

 

Sample

Input

2

100 3 2

30 20 40

50 30 50

100 2 3

1 1

2 2

3 3

 

Output

Case 1

1

Case 2

-1

--------------------------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int A[100][100];
int s,k,n;
int result;
int backtrack(int ck, int totalScore, int pre){
	if(ck==k){
		if(totalScore==s){
			result++;
			return 0;
		}
		
	}
	else{
		for(int i=1; i<=n;i++){
			if(A[i][ck+1]>=pre && (totalScore+A[i][ck+1])<=s){
				backtrack(ck+1, totalScore+A[i][ck+1], A[i][ck+1]);
			}
		}
		return 0;
	}
}
int main(){
	//freopen("in.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cin>>s>>k>>n;
		
		for(int i=1; i<=n; i++){
			for(int j=1; j<=k; j++) cin>>A[i][j];
		}
		cout<<"Case "<<tc<<endl;
		
		int kq = -1;
		result = 0;
		for(int i=1; i<=n; i++){
			int h= backtrack(1,A[i][1],A[i][1]);
		}
		if(result==0) result =-1;
		cout<<result<<endl;
	}
	return 0;
}