Untitled

Di chuyển bò
Toản có một đàn bò, Toản muốn di chuyển đàn bò đi nơi khác bằng một chiếc xe tải có tải trọng (300kg < C < 3000kg).  Anh ta muốn di chuyển được khối lượng lớn nhất mà không quá trọng tải của xe. Cho số lượng bò là N (5 < N < 16) và khối lượng của mỗi con. Xác định khối lượng tối đa mà có thể di chuyển được.

 

Input

Dòng đầu tiên số T là số trường hợp test.

Với mỗi trường hợp dòng đầu gồm 2 số M, N là trọng tải của xe và số bò.

Dòng thứ 2 là khối lượng của các con bò.

 

Output

Với mỗi trường hợp gồm “#” và số trường hợp test và kết quả trường hợp đó.

 

Sample

 

Input

2

366 5 

139 105 126 139 114 

315 5 

112 133 123 115 126

 

Output

#1 358

#2 259