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~.