Ngoài các kiến thức học trên trường, Thuận nhận thấy mình còn thiếu nội dung kiến thức. Qua tìm hiểu Thuận biết rằng, để bổ sung nội dung kiến thức thứ \(i (1 \le i \le n)\) , Thuận cần tham gia khóa học với chi phí là \(c_i\). Thuận đang dự định làm sản phẩm, sản phẩm thứ \(j (1 \le j \le m)\) sẽ đòi hỏi kiến thức sau:
\(s_{j_1}, s_{j_2}, ..., s_{j_{p_j}}\) (1 \le \(s_{j_1} < s_{j_2} < ... < s_{j_{p_j}} \le n\)) và nếu hoàn thành xong sản phẩm này Thuận sẽ bán và thu về được số tiền là \(t_j\) .Sắp tới, Thuận sẽ đăng kí học một số khóa học (hoặc không đăng kí học khóa học nào) và với các kiến thức mới đó Thuận sẽ làm tất các sản phẩm có thể làm được.

Yêu cầu: Gọi \(X\) là tổng chi phí tham gia các khóa học, \(Y\) là tổng tiền thu được từ các sản
phẩm mà Thuận có thể làm được, hãy giúp Thuận đăng kí các môn học để \(|Y - X|\) đạt giá trị
lớn nhất.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n, m\);
• Dòng thứ hai gồm \(n\) số nguyên \(c_1, c_2, ..., c_n (1 \le c_i \le 10^6)\);
• Dòng thứ \(j (1 \le j \le m)\) trong \(m\) dòng tiếp theo mô tả thông tin về sản phẩm thứ \(j\) có khuôn dạng:
  • Đầu tiên là số nguyên \(t_j (t_j \le 10^6)\);
  • Tiếp theo là số nguyên \(p_j\);
  • Tiếp theo là \(p_j\) số nguyên \(s_{j_1}, s_{j_2}, ..., s_{j_{p_j}}\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị \(Y - X\) lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\) và \(m \le 100\);
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\) và \(m \le 20\);
• Subtask \(3\) (\(30\%\) số điểm): \(n, m \le 100\) và \(p_j = 2\);
• Subtask \(4\) (\(30\%\) số điểm): \(n, m \le 1000\).

Example

3 3
1 2 3
2 2 1 3
5 2 1 3
1 1 2

3

3 3
3 3 3
1 2 1 2
1 2 1 3
1 1 2

0