Sân vận động Quốc gia Mỹ Đình là nơi diễn ra nhiều trận bóng đá của đội tuyển Việt Nam trong các giải đấu tầm khu vực. Do được xây dựng đã lâu, hệ thống chiếu sáng của sân vận động đã xuống cấp, không đảm bảo tiêu chuẩn về ánh sáng cho các trận đấu được diễn ra vào buổi tối.

Để khắc phục tình trạng này, ban quảy lý sân vận động quyết định xây thêm một số giàn đèn xung quanh sân. Sân vận động được mô phỏng dưới dạng hình chữ nhật, được chia làm ~m~ hàng và ~n~ cột. Một giàn đèn, nếu được lắp đặt sẽ giúp chiếu sáng toàn bộ các ô trên một hàng hoặc một cột của sân. Ban quản lý sẽ lắp đặt một hoặc nhiều giàn đèn khác nhau. Chi phí lắp đặt được xác định như sau: Để lắp giàn đèn chiếu sáng cho hàng ~1, 2, \ldots, m~ mất lần lượt ~r_1, r_2, \ldots, r_m~ đồng. Để lắp giàn đèn chiếu sáng cho cột ~1, 2, \ldots, n~ mất ~c_1, c_2, \ldots, c_n~ đồng.

Khảo sát thực trạng, ban quản lý nhận ra có một số vị trí trên sân hiện đang bị thiếu ánh sáng nghiêm trọng. Ánh sáng tại những ô này bắt buộc phải được cải thiện và hệ thống giàn đèn xây dựng thêm phải chiếu sáng được toàn bộ các ô này. Các bạn hãy giúp ban quản lý lựa chọn vị trí lắp đặt giàn đèn sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên ~\theta~ ~(1 \leq \theta \leq 5)~ là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên ~m~ và ~n~ ~(1 \leq m, n \leq 2207)~ cho biết kích thước hai chiều của sân vận động.
• Dòng thứ ba chứa ~m~ số nguyên ~r_1, r_2, \ldots, r_m~ ~(1 \leq r_i \leq 10^9)~ là chi phí để lắp đặt giàn đèn chiếu sáng cho các hàng.
• Dòng thứ tư chứa ~n~ số nguyên ~c_1, c_2, \ldots, c_n~ ~(1 \leq c_j \leq 10^9)~ là chi phí để lắp đặt giàn đèn chiếu sáng cho các cột.
• ~m~ dòng cuối cùng, mỗi dòng gồm một xâu nhị phân độ dài ~n~. Ký tự thứ ~j~ ở dòng thứ ~i~ là 1 khi và chỉ khi ô ở hàng ~i~ và cột ~j~ phải được chiếu sáng.

Output

• Dòng đầu tiên chứa một số nguyên là tổng chi phí tối thiểu để lắp đặt giàn đèn.
• Dòng thứ hai chứa số nguyên ~x~ cho biết số giàn đèn chiếu sáng hàng được lắp đặt; theo sau là ~x~ số nguyên thể hiện chỉ số của các hàng được lắp giàn đèn.
• Dòng thứ ba chứa số nguyên ~y~ cho biết số giàn đèn chiếu sáng cột được lắp đặt; theo sau là ~y~ số nguyên thể hiện chỉ số của các cột được lắp giàn đèn.

Nếu có nhiều phương án tối ưu, bạn được in ra một đáp án bất kỳ.

Giới hạn

• Subtask ~1~ (~15~ điểm): Tất cả ~m \cdot n~ ô đều phải được chiếu sáng.
• Subtask ~2~ (~15~ điểm): ~m, n \leq 10~
• Subtask ~3~ (~15~ điểm): Số ô phải được chiếu sáng không quá ~20~
• Subtask ~4~ (~15~ điểm): ~m \leq 15~
• Subtask ~5~ (~40~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

2
3 4
2 2 7
1 9 9 7
1011
0100
1011

Sample Output 1

11
3 1 2 3
0

Sample Input 2

2
3 5
7 8 9
1 2 3 4 5
01010
10101
00000

Sample Output 2

14
1 2
2 2 4

Sample Input 3

5
7 21
20000000 2000000 70000 1000 900 90 7
100000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
111111111111111111111
100001110111011011101
101110110111011011101
100001111010111000001
101111111010111011101
101111111101111011101
111111111111111111111

Sample Output 3

22071997
7 1 2 3 4 5 6 7
0

Sample Input 4

2
1 1
1000000000
1000000000
0

Sample Output 4

0
0
0