Untitled

Hugo thi chạy

Sắp tới công ty nên Hugo làm việc tổ chức sự kiện Olympic dành cho toàn bộ nhân viên. Có rất nhiều bộ môn thi đấu như Bóng bàn, cầu long, cờ vua, cờ tướng, bơi lội, và có cả thể thao điện tử nữa. Là một người quan tâm tới sức khỏe của bản thân vì vậy Hugo thường xuyên chạy bộ để rèn luyện sức khỏe. Thật may trong các môn thi đấu Olympic có hạng mục này. Trong quá trình tập luyện Hugo đã luyện cho mình được 5 kiểu chạy khác nhau, mỗi kiểu chạy sẽ tiêu tốn số lượng năng lượng nhất định và thời gian chạy hết 1km là khác nhau. Mỗi kiểu chạy sẽ sử dụng cho 1km.

Năng lượng của Hugo là có hạn, nếu sử dụng vượt Hugo sẽ bị bệnh.


Sau khi tham khảo thông tin Hugo biết được quãng đường cần chạy bộ D của cuộc thi. Nhân viên y tế có thể giúp Hugo tính toán được số năng lượng tối đa của Hugo.
Cho thông tin của 5 kiểu chạy của Hugo bao gồm số phút, số giây (số phút <= 6 và số giây <= 60) và số năng lượng tiêu tốn.
Hãy tính thời gian ngắn nhất để Hugo về đích mà không bị bệnh.

 

Input

Dòng đầu số test T (T<=50)

Mỗi test bao gồm 2 dòng

Dòng 1 chứa số năng lượng tối đa M <=60 và chiều dài quãng đường D<=40km
Dòng thứ 2 chứa thông tin của 5 kiểu chạy lần lượt là số phút, số giây, số năng lượng tiêu tốn

 

Output
In ra thời gian ngắn nhất để Hugo về đích mà không bị bệnh theo dạng số phút, số giây. Nếu không thể hãy in ra -1

 

Input

4

297 10

5 38 23 5 22 12 4 16 6 5 38 20 0 20 17

192 10

2 6 12 6 5 24 2 22 22 4 13 12 4 30 16

503 10

1 42 20 1 8 14 0 33 15 2 6 6 5 3 16

122 10

2 37 21 3 59 22 6 0 22 4 56 5 0 9 10

 

Output

Case #1

3 20

Case #2

21 0

Case #3

5 30

Case #4

1 30


10 10 0 9
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 1 1
20 20 130 709
1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 1 1
10 18 0 100
1 1 0.33 1 2 0.67 2 2 0.82 2 3 0.18 3 3 0.52 3 4 0.48 4 4 0.83 4 5 0.17 5 5 0.0 5 6 1.0 6 6 0.15 6 7 0.85 7 7 0.4 7 8 0.6 8 8 0.03 8 9 0.97 9 9 0.76 9 10 0.24
10 19 249 1000
1 1 0.81 1 2 0.19 2 2 0.96 2 3 0.04 3 3 0.32 3 4 0.68 4 4 0.61 4 5 0.39 5 5 0.72 5 6 0.28 6 6 0.41 6 7 0.59 7 7 0.51 7 8 0.49 8 8 0.82 8 9 0.18 9 9 0.77 9 10 0.23 10 10 1
30 58 999 1000
8 8 0.14 21 21 0.74 2 2 0.58 1 2 0.26 3 4 0.02 12 13 0.43 6 7 0.52 16 17 0.85 20 20 0.87 25 25 0.36 2 3 0.42 26 27 0.73 20 21 0.13 4 5 0.48 12 12 0.57 9 10 0.81 6 6 0.48 1 1 0.74 3 3 0.98 28 28 0.69 23 23 0.05 10 11 0.86 10 10 0.14 25 26 0.64 21 22 0.26 5 5 0.37 28 29 0.31 17 18 0.28 11 11 0.95 15 15 0.48 26 26 0.27 17 17 0.72 18 18 0.89 11 12 0.05 13 14 0.8 9 9 0.19 8 9 0.86 19 20 0.97 15 16 0.52 24 24 0.15 13 13 0.2 29 30 0.25 22 22 0.82 18 19 0.11 27 27 0.42 16 16 0.15 4 4 0.52 27 28 0.58 22 23 0.18 29 29 0.75 19 19 0.03 7 7 0.81 24 25 0.85 14 15 0.8 23 24 0.95 7 8 0.19 5 6 0.63 14 14 0.2
50 99 741 1000
1 2 0.34 20 21 0.3 39 40 0.35 25 25 0.13 40 41 0.28 43 43 0.43 40 40 0.72 35 36 0.43 36 36 0.0 34 35 0.07 13 14 0.05 19 20 0.95 19 19 0.05 47 47 0.89 30 31 0.18 12 13 1.0 25 26 0.87 7 8 0.05 48 48 0.24 7 7 0.95 5 5 0.48 49 50 0.43 3 3 0.37 2 3 0.47 34 34 0.93 45 46 0.25 26 27 0.27 38 38 0.79 47 48 0.11 32 33 0.87 8 8 0.41 43 44 0.57 33 34 0.94 12 12 0.0 13 13 0.95 11 11 0.63 46 47 0.07 4 5 0.56 6 7 0.88 20 20 0.7 44 44 0.13 21 21 0.79 24 25 0.61 37 37 0.1 42 42 0.17 15 15 0.97 38 39 0.21 48 49 0.76 14 15 0.29 8 9 0.59 28 28 0.85 41 42 0.41 4 4 0.44 32 32 0.13 27 28 0.65 27 27 0.35 17 18 0.52 46 46 0.93 16 16 0.62 18 19 0.06 5 6 0.52 17 17 0.48 24 24 0.39 23 24 0.6 6 6 0.12 9 10 0.54 10 11 0.8 31 31 0.01 22 22 0.07 14 14 0.71 16 17 0.38 33 33 0.06 35 35 0.57 49 49 0.57 30 30 0.82 36 37 1.0 9 9 0.46 21 22 0.21 26 26 0.73 50 50 1 44 45 0.87 28 29 0.15 45 45 0.75 2 2 0.53 31 32 0.99 29 30 0.45 29 29 0.55 1 1 0.66 15 16 0.03 37 38 0.9 42 43 0.83 41 41 0.59 18 18 0.94 22 23 0.93 3 4 0.63 23 23 0.4 10 10 0.2 39 39 0.65 11 12 0.37
10 100 13 1000
1 1 0.07 1 2 0.13 1 3 0.1 1 4 0.12 1 5 0.08 1 6 0.1 1 7 0.11 1 8 0.11 1 9 0.05 1 10 0.13 2 1 0.08 2 2 0.11 2 3 0.09 2 4 0.13 2 5 0.08 2 6 0.12 2 7 0.09 2 8 0.11 2 9 0.11 2 10 0.08 3 1 0.07 3 2 0.11 3 3 0.15 3 4 0.07 3 5 0.1 3 6 0.11 3 7 0.08 3 8 0.13 3 9 0.08 3 10 0.1 4 1 0.1 4 2 0.18 4 3 0.06 4 4 0.11 4 5 0.09 4 6 0.11 4 7 0.06 4 8 0.1 4 9 0.09 4 10 0.1 5 1 0.09 5 2 0.13 5 3 0.13 5 4 0.09 5 5 0.11 5 6 0.07 5 7 0.08 5 8 0.05 5 9 0.12 5 10 0.13 6 1 0.13 6 2 0.06 6 3 0.07 6 4 0.14 6 5 0.08 6 6 0.15 6 7 0.13 6 8 0.1 6 9 0.05 6 10 0.09 7 1 0.11 7 2 0.14 7 3 0.08 7 4 0.09 7 5 0.06 7 6 0.13 7 7 0.1 7 8 0.11 7 9 0.1 7 10 0.08 8 1 0.06 8 2 0.08 8 3 0.04 8 4 0.12 8 5 0.12 8 6 0.1 8 7 0.12 8 8 0.1 8 9 0.06 8 10 0.2 9 1 0.15 9 2 0.11 9 3 0.09 9 4 0.14 9 5 0.03 9 6 0.06 9 7 0.08 9 8 0.1 9 9 0.12 9 10 0.12 10 1 0.08 10 2 0.03 10 3 0.07 10 4 0.16 10 5 0.1 10 6 0.13 10 7 0.15 10 8 0.08 10 9 0.07 10 10 0.13
10 100 242 1000
7 7 0.08 2 8 0.15 10 4 0.08 8 4 0.18 5 1 0.04 6 2 0.13 10 3 0.09 7 2 0.07 10 5 0.06 8 7 0.11 10 2 0.1 7 8 0.13 3 7 0.1 5 10 0.07 4 2 0.04 8 3 0.08 4 5 0.1 2 2 0.07 4 6 0.12 2 10 0.06 6 7 0.06 4 1 0.16 6 8 0.11 4 8 0.14 10 6 0.16 3 4 0.12 3 8 0.09 1 6 0.1 6 3 0.08 9 10 0.16 5 8 0.15 9 7 0.1 4 9 0.09 6 6 0.13 1 5 0.15 3 2 0.09 9 8 0.11 1 2 0.08 8 1 0.11 5 2 0.07 4 7 0.06 1 1 0.08 3 10 0.11 4 10 0.09 3 5 0.09 2 5 0.08 8 9 0.09 9 3 0.08 3 6 0.1 7 3 0.09 1 10 0.1 5 7 0.14 6 5 0.17 10 9 0.03 4 4 0.13 5 4 0.1 2 4 0.07 7 6 0.13 9 4 0.08 7 1 0.04 10 1 0.11 8 10 0.04 5 6 0.11 4 3 0.07 8 6 0.09 7 4 0.07 2 7 0.13 1 7 0.12 2 1 0.15 2 3 0.1 1 4 0.06 9 9 0.12 7 9 0.08 9 1 0.09 6 1 0.07 2 6 0.08 8 5 0.12 5 5 0.15 6 9 0.07 9 6 0.09 10 10 0.13 8 2 0.12 7 10 0.14 3 3 0.08 9 2 0.07 5 3 0.09 8 8 0.06 5 9 0.08 2 9 0.11 1 3 0.1 10 7 0.13 9 5 0.1 10 8 0.11 6 4 0.09 3 9 0.14 1 9 0.12 7 5 0.17 3 1 0.08 1 8 0.09 6 10 0.09
100 200 498 1000
58 57 0.25 86 85 0.77 93 92 0.71 71 72 0.64 68 67 0.16 95 94 0.34 45 44 0.97 92 91 0.64 89 90 0.28 11 12 0.62 37 36 0.36 24 23 0.69 65 66 0.52 13 12 0.47 20 21 0.53 46 47 0.15 19 18 0.2 24 25 0.31 41 40 0.51 79 80 0.47 17 16 0.76 44 43 0.2 69 68 0.64 9 8 0.31 22 23 0.86 91 90 0.32 35 34 0.95 78 79 0.91 64 63 0.98 42 43 0.52 81 80 0.32 39 38 0.46 85 86 0.02 7 6 0.7 29 28 0.37 49 48 0.33 20 19 0.47 2 3 0.53 3 4 0.75 100 99 0.08 26 25 0.47 88 87 0.56 53 54 0.55 98 99 0.01 74 73 0.65 68 69 0.84 23 22 0.59 81 82 0.68 28 27 0.26 54 53 0.73 62 63 0.2 9 10 0.69 76 77 0.18 83 84 0.35 72 73 0.21 25 24 0.83 42 41 0.48 74 75 0.35 61 62 0.84 26 27 0.53 75 76 0.86 84 85 0.57 71 70 0.36 66 67 0.86 75 74 0.14 82 83 0.71 63 64 0.63 59 58 0.78 83 82 0.65 2 1 0.47 40 41 0.96 23 24 0.41 62 61 0.8 78 77 0.09 30 31 0.51 55 56 0.62 29 30 0.63 34 33 0.54 87 88 0.27 25 26 0.17 3 2 0.25 69 70 0.36 52 51 0.21 88 89 0.44 51 50 0.11 63 62 0.37 50 49 0.62 31 30 0.9 8 7 0.56 21 20 0.67 77 76 0.52 41 42 0.49 46 45 0.85 37 38 0.64 32 33 0.22 27 26 0.75 50 51 0.38 60 61 0.18 4 5 0.07 18 17 0.07 79 78 0.53 55 54 0.38 94 93 0.93 60 59 0.82 17 18 0.24 97 98 0.91 61 60 0.16 97 96 0.09 96 95 0.8 73 72 0.06 85 84 0.98 16 15 0.31 48 49 0.45 43 44 1.0 100 1 0.92 90 89 0.95 54 55 0.27 39 40 0.54 84 83 0.43 47 46 0.53 32 31 0.78 48 47 0.55 19 20 0.8 66 65 0.14 1 100 0.03 27 28 0.25 47 48 0.47 96 97 0.2 21 22 0.33 80 79 0.49 80 81 0.51 30 29 0.49 12 11 0.39 36 35 0.06 7 8 0.3 16 17 0.69 5 6 0.71 33 32 0.65 82 81 0.29 11 10 0.38 15 14 0.44 67 68 0.96 57 56 0.44 70 69 0.17 5 4 0.29 45 46 0.03 99 98 0.83 70 71 0.83 57 58 0.56 8 9 0.44 94 95 0.07 98 97 0.99 13 14 0.53 34 35 0.46 53 52 0.45 4 3 0.93 52 53 0.79 86 87 0.23 6 7 0.26 87 86 0.73 73 74 0.94 33 34 0.35 38 39 0.94 58 59 0.75 36 37 0.94 28 29 0.74 51 52 0.89 14 13 0.03 59 60 0.22 89 88 0.72 31 32 0.1 92 93 0.36 64 65 0.02 1 2 0.97 95 96 0.66 12 13 0.61 76 75 0.82 18 19 0.93 38 37 0.06 93 94 0.29 99 100 0.17 10 9 0.55 43 42 0.0 15 16 0.56 44 45 0.8 22 21 0.14 65 64 0.48 90 91 0.05 56 57 0.43 77 78 0.48 35 36 0.05 72 71 0.79 14 15 0.97 49 50 0.67 56 55 0.57 6 5 0.74 10 11 0.45 91 92 0.68 40 39 0.04 67 66 0.04
100 200 802 1000
15 16 0.79 84 83 0.45 49 50 0.93 76 77 0.8 36 35 0.21 77 76 0.8 7 6 0.74 10 9 0.42 51 52 0.99 14 15 0.55 41 42 0.44 79 78 0.73 13 12 0.52 42 43 0.2 82 83 0.62 74 75 0.74 62 61 0.25 96 95 0.25 29 30 0.35 53 54 0.88 52 51 0.01 50 49 0.07 79 80 0.27 39 38 0.0 9 10 0.31 19 18 0.21 27 28 0.51 97 98 0.67 57 58 0.18 88 87 0.73 83 84 0.6 77 78 0.2 53 52 0.12 66 67 0.91 49 48 0.07 3 2 0.47 89 88 0.11 22 21 0.79 64 63 0.17 22 23 0.21 43 44 0.96 37 38 0.81 87 88 0.64 70 71 0.43 11 10 0.67 76 75 0.2 54 55 0.43 18 17 0.85 56 57 0.24 46 45 0.18 93 92 0.8 69 70 0.9 78 79 0.73 60 59 0.67 71 72 0.84 16 15 0.92 58 59 0.54 47 46 0.97 45 46 0.18 52 53 0.99 32 31 0.8 99 98 0.82 56 55 0.76 23 22 0.82 35 34 0.77 24 25 0.15 8 7 0.34 54 53 0.57 46 47 0.82 51 50 0.01 4 3 0.16 91 90 0.65 9 8 0.69 30 31 0.21 11 12 0.33 43 42 0.04 6 7 0.92 20 19 0.37 61 62 0.51 89 90 0.89 7 8 0.26 29 28 0.65 44 43 0.38 59 58 0.26 80 81 0.54 75 74 0.93 37 36 0.19 90 89 0.61 23 24 0.18 73 74 0.9 25 24 0.41 17 16 0.34 10 11 0.58 84 85 0.55 94 95 0.55 27 26 0.49 8 9 0.66 32 33 0.2 66 65 0.09 57 56 0.82 26 27 0.11 61 60 0.49 90 91 0.39 68 69 0.38 18 19 0.15 97 96 0.33 72 71 0.75 94 93 0.45 34 33 0.83 33 32 0.6 78 77 0.27 63 64 0.93 5 6 0.4 80 79 0.46 48 49 0.03 58 57 0.46 64 65 0.83 63 62 0.07 82 81 0.38 100 1 0.58 99 100 0.18 2 1 0.41 88 89 0.27 24 23 0.85 92 91 0.57 62 63 0.75 55 56 0.52 28 29 0.5 12 13 0.27 38 37 0.81 65 64 0.49 1 100 0.36 83 82 0.4 45 44 0.82 31 32 0.33 96 97 0.75 42 41 0.8 73 72 0.1 21 22 0.3 4 5 0.84 98 99 0.6 30 29 0.79 14 13 0.45 41 40 0.56 91 92 0.35 85 86 0.52 85 84 0.48 34 35 0.17 100 99 0.42 31 30 0.67 70 69 0.57 87 86 0.36 28 27 0.5 81 82 0.41 44 45 0.62 50 51 0.93 1 2 0.64 67 66 0.95 35 36 0.23 86 85 0.99 75 76 0.07 93 94 0.2 3 4 0.53 67 68 0.05 47 48 0.03 55 54 0.48 95 94 0.54 38 39 0.19 5 4 0.6 21 20 0.7 68 67 0.62 65 66 0.51 40 41 0.07 2 3 0.59 19 20 0.79 86 87 0.01 17 18 0.66 15 14 0.21 40 39 0.93 69 68 0.1 95 96 0.46 13 14 0.48 59 60 0.74 20 21 0.63 36 37 0.79 98 97 0.4 12 11 0.73 81 80 0.59 72 73 0.25 26 25 0.89 74 73 0.26 92 93 0.43 25 26 0.59 39 40 1.0 33 34 0.4 6 5 0.08 60 61 0.33 71 70 0.16 16 17 0.08 48 47 0.97


#include<iostream>
using namespace std;
int T, nx, ny, cx, cy;
int n, arr[15][2];
int da[15][15];
int visit[15];
int rs;
void nhap() {
	cin >> cx >> cy >> nx >> ny;
	cin >> n;
	arr[0][0] = cx; arr[0][1] = cy;
	for(int i = 1; i < n+1; i ++) {
		cin >> arr[i][0] >> arr[i][1];
	}
}
void reset(){
	for(int i = 0; i < n+1; i ++) {
		for(int j = 0; j < n+1; j ++) {
			da[i][j] = 0;
		}
		visit[i] = 0;
	}
	visit[0] = 1;
}
int abs(int x, int y) {
	if(x>y) return x-y; 
	return y-x;
}
int process(int x1, int y1, int x2, int y2) {
	return abs(x1,x2) + abs(y1,y2);
}
void tt() {
	for(int i = 0; i < n+1; i ++) {
		for(int j = 0; j < n+1; j ++) {
			da[i][j] = process(arr[i][0],arr[i][1],arr[j][0],arr[j][1]);
		}
	}
}
void backtrack(int gg=0, int x=0, int count=0){
	if(gg==n){
		int ss = count + process(arr[x][0],arr[x][1],nx,ny);
		if(rs > ss) rs = ss;
		return;
	}
	if(count + process(arr[x][0],arr[x][1],nx,ny) > rs) return;
	for(int i = 0; i < n+1; i ++){
		if(visit[i] == 0) {
			visit[i] = 1;
			backtrack(gg+1,i,count+da[x][i]);
			visit[i] = 0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(int t = 1; t <= T; ++t)
	{
		nhap(); 
		reset();
		tt(); 
		rs = 1000000000;
		backtrack();
		cout << "Case #" << t << " " << rs << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}