Công ty VNG đang tiến hành thử nghiệm ~N~ sản phẩm trò chơi mới. Khi phát hành một sản phẩm, công ty sẽ được tài trợ một số tiền nhất định từ các nhà đầu tư. Nếu phát hành sản phẩm thứ ~i~ sẽ được tài trợ ~P_i~ đô la. Tuy nhiên, để phát hành một sản phẩm, công ty cần phải sử dụng một số tài nguyên như máy chủ, cơ sở dữ liệu, nhân lực, v.v. Để sử dụng một tài nguyên, công ty cần phải trả một khoản phí nhất định. Có tất cả ~M~ loại tài nguyên khác nhau, và chi phí khi sử dụng tài nguyên thứ ~j~ là ~C_j~ đô la.

Bạn là một nhà quản lý tài ba với khả năng lập trình siêu việt, công ty giao cho bạn một nhiệm vụ quan trọng, đó là xác định những sản phẩm nào nên phát hành và sử dụng những loại tài nguyên nào để tối đa hoá lợi nhuận. Lợi nhuận được tính bằng tổng số tiền được tài trợ trừ đi tổng số tiền phải trả cho việc sử dụng tài nguyên. Lưu ý, một sản phẩm chỉ có thể được phát hành khi có đủ bộ tài nguyên yêu cầu, và một loại tài nguyên có thể sử dụng chung cho các sản phẩm khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N, M \le 1000~)
• Dòng thứ hai chứa ~N~ số nguyên thể hiện số tiền được tài trợ cho các sản phẩm ~p_1, p_2, ..., p_N~ ~(1 \le p_i \le 10^6)~
• Dòng thứ ba chứa ~M~ số nguyên thể hiện chi phí khi sử dụng các tài nguyên ~c_1, c_2, ..., c_M~ ~(1 \le c_j \le 10^6)~
• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số ~a_{i1}, a_{i2}, ..., a_{iM}~ với ~a_{ij} = 1~ nếu sản phẩm thứ ~i~ cần sử dụng tài nguyên thứ ~j~, ngược lại ~a_{ij} = 0~ nếu không cần sử dụng.

Output

• Dòng đầu tiên ghi tổng số tiền lợi nhuận tối đa có thể đạt được.
• Dòng thứ 2 liệt kê danh sách các sản phẩm được phát hành (nếu không có sản phẩm nào được phát hành, in ra 0)
• Dòng thứ 3 liệt kê danh sách các tài nguyên được sử dụng (nếu không có tài nguyên nào được sử dụng, in ra 0)

Subtasks

• Subtask 1 (25%): ~N, M \le 20~
• Subtask 2 (25%): ~N \le 20~ hoặc ~M \le 20~
• Subtask 3 (25%): ~N, M \le 100~
• Subtask 4 (25%): Không có ràng buộc gì thêm

Nếu chỉ tìm được tổng lợi nhuận tối đa, thì được ~50\%~ số điểm.

Sample

Input

3 4
4 10 11
6 2 3 7
1 0 0 1
0 1 1 0
0 1 0 0

Output

16
2 3
2 3

Giải thích

Các thí nghiệm được thực hiện là 2 và 3. Các dụng cụ cần sử dụng là 2 và 3.