Trong xử lý tín hiệu, ta đôi khi cần tìm giá trị lớn nhất của một biểu thức chứa các phép toán AND và OR theo bit, khi mỗi biến nguyên chỉ được chọn trong một đoạn cho trước.

Biểu thức gồm \(P\) biểu thức con đặt trong ngoặc và nối với nhau bằng phép AND theo bit (&). Mỗi biểu thức con gồm một hoặc nhiều biến nối với nhau bằng phép OR theo bit (|). Các biến được đánh số theo thứ tự xuất hiện. Chẳng hạn, nếu số biến trong bốn biểu thức con lần lượt là \(3,1,2,2\) thì

Hãy tìm giá trị lớn nhất mà biểu thức có thể nhận.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(P\), lần lượt là tổng số biến và số biểu thức con.

Dòng tiếp theo chứa \(P\) số nguyên \(K_1,K_2,\ldots,K_P\), trong đó \(K_i\) là số biến của biểu thức con thứ \(i\). Mỗi \(K_i\ge 1\) và tổng các \(K_i\) bằng \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(A_j,B_j\), quy định

Dữ liệu ra

In một số nguyên duy nhất: giá trị lớn nhất của biểu thức.

Ràng buộc

• \(1\le P\le N\le 100\).
• \(0\le A_j\le B_j\le 2\,000\,000\,000\).

Phân nhóm

• \(30\%\) số bộ dữ liệu có ít hơn một triệu cách gán các biến.

Ví dụ

8 4
3 1 2 2
2 4
1 4
0 0
1 7
1 4
1 2
3 4
2 3

6