Cho \(n\) dự án được đánh chỉ số từ \(1\) đến \(n\) và \(m\) cỗ máy được đánh chỉ số từ \(1\) đến \(m\). Dự án thứ \(i\) thu về \(a_i\) đồng và cỗ máy thứ \(j\) mất \(b_j\) đồng để mua. Mỗi dự án yêu cầu một số cỗ máy và mỗi cỗ máy có thể được dùng chung cho một số dự án. Hãy chọn một số dự án và mua một số cỗ máy sao cho số tiền thu được là tối đa.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 10^3)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\).
• Dòng tiếp theo chứa \(m\) số nguyên \(b_1, b_2, \ldots, b_m\) \((1 \leq b_i \leq 10^9)\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(k_i\) và \(k_i\) số nguyên phân biệt \(c_{i_1}, c_{i_2}, ..., c_{i_k}\) \((1 \leq k_i \leq \min(10, m), 1 \leq c_{i_j} \leq m)\) nghĩa là dự án thứ \(i\) yêu cầu \(k_i\) cỗ máy \(c_{i_1}, c_{i_2}, ..., c_{i_k}\).

Output

• Dòng đầu tiên chứa số tiền tối đa thu được.
• Dòng tiếp theo chứa số lượng và chỉ số của những dự án được chọn.
• Dòng tiếp theo chứa số lượng và chỉ số của những cỗ máy được mua.
• Nếu có nhiều đáp án, hãy in một đáp án bất kỳ.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, m \leq 20\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.
• Bạn sẽ được \(50\%\) số điểm của test nếu in đúng số tiền tối đa thu được và \(100\%\) số điểm của test nếu in đúng toàn bộ.

Example

4 4
3 6 3 2
8 6 1 3
2 1 4
2 3 4
4 1 2 3 4
1 1

2
1 2
2 3 4