Korn là một lập trình viên giỏi thất nghiệp, nhưng anh lại rất tự cao. Hôm nay anh tham gia phỏng vấn tại công ty công nghệ mới nổi mang tên Biker.

Tại đây, anh được yêu cầu xây dựng một dãy nhị phân độ dài ~n~ thỏa mãn ~q~ tính chất. Mỗi tính chất gồm 6 số nguyên ~i_{1}, v_{1}, i_{2}, v_{2}, i_{3}, v_{3}~ ~(1 \leq i_1, i_2, i_3 \leq n~, ~0 \leq v_{1}, v_{2}, v_{3} \leq 1)~ với ý nghĩa:

• Giá trị của bit thứ ~i_{1}~ là ~v_{1}~

• Giá trị của bit thứ ~i_{2}~ là ~v_{2}~

• Giá trị của bit thứ ~i_{3}~ là ~v_{3}~

Một tính chất gọi là được thỏa mãn nếu ít nhất hai điều kiện trong ba điều kiện trên đúng.

Để được nhận vào làm, Korn cần phải vượt qua bài kiểm tra một cách xuất sắc. Tuy nhiên do thất nghiệp quá lâu quá giỏi, anh ta không biết làm mà lại đi nhờ bạn làm giúp thách đố bạn làm được.

Yêu cầu: Bạn hãy tìm một dãy nhị phân thỏa mãn các điều kiện trên để cho Korn hết tự cao nhé.

Input

Vào từ file văn bản recruit.inp:

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ ~(3 \leq n, q \leq 10^{5})~ là độ dài dãy nhị phân và số yêu cầu.

• ~q~ dòng tiếp theo, mỗi dòng chứa 6 số nguyên ~i_{1}, v_{1}, i_{2}, v_{2}, i_{3}, v_{3}~ ~(1 \leq i_1, i_2, i_3 \leq n~, ~0 \leq v_{1}, v_{2}, v_{3} \leq 1)~ cho biết một yêu cầu.

Output

Đưa ra file văn bản recruit.out:

• Nếu không thể dựng được dãy nhị phân như vậy, hãy in ra ~-1~.

• Ngược lại, in ra xâu nhị phân tìm được bất kỳ.

Scoring

Sample Input 1

7 5
3 0 5 0 6 1
1 1 2 1 3 0
4 0 5 1 6 1
5 0 6 1 7 1
1 0 2 0 4 0

Sample Output 1

1000111

Sau thất bại tại cuộc thi CPCI Lanoiger 3202, oJoJ quyết tâm sang năm sẽ comeback cực mạnh bằng việc luyện 10 bài A div 2 mỗi ngày. Tuy nhiên, ngay ở bài A đầu tiên, cậu đã gặp phải một thách thức lớn.

Bạn có một dãy số ~A~ với độ dài ~N~. Bạn cần thực hiện ~M~ truy vấn có dạng: cho hai số nguyên ~l, r~ (~1 \le l \le r \le N~), hãy tìm giá trị lớn nhất trong dãy con ~A_l, A_{l + 1} \dots, A_r~.

Tuy nhiên, dãy số ~A~ không được cho trước, và bạn cần phải xây dựng dãy số trên.

Với mỗi ~i~ từ ~1~ đến ~N~, bạn có thể chọn một trong ~K_i~ số ~V_{i, j}~ làm giá trị của ~A_i~, với chi phí tương ứng là ~C_{i, j}~.

Sau khi xử lý tất cả các truy vấn, số điểm của bạn sẽ là tổng kết quả của tất cả các truy vấn trên, trừ đi chi phí chọn các giá trị ~A_i~.

Yêu cầu: Hãy tính số điểm tối đa có thể đạt được.

Input

Dữ liệu vào từ file văn bản genarray.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ (~1 \le N \le 300, 1 \le M \le 10^5~).

• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~l_i, r_i~ (~1 \le l_i \le r_i \le N~) mô tả một truy vấn.

• Tiếp theo là mô tả các giá trị mà ~A_i~ có thể nhận với ~i~ từ ~1~ đến ~N~. Mô tả thứ ~i~ có dạng:

  • Dòng đầu tiên gồm số nguyên dương ~K_i~ là số lượng giá trị có thể chọn của ~A_i~.

  • Dòng thứ ~j~ trong ~K_i~ dòng tiếp theo gồm hai số nguyên ~V_{i, j}~ và ~C_{i, j}~, tương ứng là một giá trị có thể chọn và chi phí phải trả (~0 \le V_{i, j} \le 10^8, 0 \le V_{i, j} \le 10^{13}~).

  Đầu vào đảm bảo tổng của các ~K_i~ không vượt quá ~3 \cdot 10^5~.

Output

Kết quả in ra file văn bản genarray.out:

• Gồm một số nguyên là số điểm lớn nhất có thể đạt được.

Scoring

Sample Input 1

5 5
1 5
2 3
1 4
2 4
3 5
2
0 25
4 26
2
8 7
4 4
2
7 25
1 1
2
0 27
1 19
2
8 7
4 18

Sample Output 1

-19

Notes

Ở ví dụ trên, dãy số được chọn là ~[0, 8, 1, 1, 8]~ với:

• Tổng chi phí chọn các phần tử trong dãy: ~25 + 7 + 1 + 19 + 7 = 59~;

• Tổng kết quả của các truy vấn: ~max(A_1 \dots, A_5) + max(A_2, A_3) + max(A_1 \dots, A_4) + max(A_2 \dots, A_4) + max(A_2 \dots, A_5) = 8 + 8 + 8 + 8 + 8 = 40~;

• Số điểm đạt được: ~40 - 59 = -19~.

Ta có thể chứng minh, không thể tìm được dãy số có số điểm lớn hơn ~-19~.

Một cuộc thi có ~n~ vận động viên và ~m~ nội dung thi đấu. Các vận động viên và nội dung thi đấu được đánh số bắt đầu từ ~1~.

Thể thức thi đấu như sau:

• Mỗi vận động viên ~i~ chọn đúng một nội dung ~j~ có ~c_{i, j} \ne -1~ để tham gia và đạt được ~c_{i, j}~ điểm.

• Mỗi nội dung thi đấu ~j~ có tối đa ~s_j~ vận động viên được tham gia.

Tìm tổng điểm lớn nhất các vận động viên có thể đạt được.

Input

Dữ liệu vào từ file văn bản olympiad.inp:

• Dòng đầu tiên gồm hai số nguyên ~n, m~ (~1 \le n \le 50000~, ~1 \le m \le 10~).

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm ~m~ số nguyên ~c_{i, 1}, c_{i, 2}, \cdots, c_{i, m}~ (~-1 \le c_{i, j} \le 10^9~).

• Dòng cuối cùng gồm ~m~ số nguyên ~s_1, s_2, \cdots, s_m~ (~1 \le s_i \le n~).

• Dữ liệu đảm bảo tồn tại cấu hình thỏa mãn thể thức thi đấu.

Output

In ra file văn bản olympiad.out một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Scoring

Sample Input 1

5 3
-1 7 -1
3 5 -1
-1 6 10
-1 -1 4
2 3 -1
2 3 5

Sample Output 1

29

Notes

Ở ví dụ trên, một cách chọn tối ưu là ~[2, 2, 3, 3, 2]~. Vận động viên thứ nhất chọn nội dung ~2~, vđv thứ hai chọn nội dung ~2~, vđv thứ ba chọn nội dung ~3~, ~\cdots~. Khi đó tổng điểm tối đa là ~29~.