Trong một trò chơi trên bảng vuông \((n + 1) \times (n + 1)\), các dòng từ trên xuống dưới được đánh số từ \(0\) đến \(n\), các cột từ trái sang phải được đánh số từ \(0\) đến \(n\), ô ở dòng thứ \(i\) và cột thứ \(j\) gọi là ô \((i, j)\). Bảng có đúng \(n\) ô chứa quà, quà thứ \(i\) (\(1 \le i \le n\)) nằm ở ô \((i, p[i])\) và có giá trị là \(c[i]\).

Ban đầu bạn ở ô \((0, 0)\), mỗi bước có thể đi sang phải hoặc đi xuống dưới một ô.

Giá trị của một đường đi là tổng giá trị của các ô chứa quà mà đường đi đó đi qua. Bạn cần tìm ra đường đi có giá trị lớn nhất.

Để tăng thêm thử thách, trò chơi có thêm \(m\) màn, mỗi màn chơi có các ô bị cấm không được đi vào là các ô nằm trong hình chữ nhật có ô trái trên là \((u, y)\) và ô phải dưới là \((x, v)\). Chú ý: Mỗi màn chơi độc lập với nhau, tức là việc cấm hình chữ nhật chỉ là giả định ở mỗi màn chơi.

Input

• Dòng đầu tiên gồm hai số nguyên \(n, m\) (\(0 \le n, m \le 3 \cdot 10^5\)).
• \(n\) dòng sau, mỗi dòng gồm hai số nguyên \(p[i]\) và \(c[i]\) (\(1 \le i \le n; 1 \le p[i] \le n; 1 \le c[i] \le 10^9\)). Dữ liệu đảm bảo rằng dãy \(p\) phân biệt.
• \(m\) dòng tiếp theo, mỗi dòng gồm bốn số nguyên \(x, y, u, v\) (\(1 \le u \le x \le n; 1 \le y \le v \le n\)) mô tả hình chữ nhật bị cấm ở màn chơi tương ứng.

Output

• Dòng đầu tiên in ra giá trị của đường đi lớn nhất khi không có hình chữ nhật bị cấm.
• \(m\) dòng tiếp theo in ra kết quả của màn chơi thêm tương ứng.

Example

3 3
2 5
3 4
1 7
1 1 1 3
1 1 3 3
1 1 1 1

9
7
0
9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(m = 0\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 1000\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc nào thêm.