Năm 20XX, kỳ thi IOI cuối cùng cũng được tổ chức tại thị trấn JOI của đất nước JOI. Một bữa tiệc sẽ được tổ chức để kỷ niệm sự kiện này. Thị trấn có \(A\) con chó được đánh số từ \(1\) đến \(A\) và \(B\) con mèo được đánh số từ \(1\) đến \(B\). Bạn muốn mời cả \(A+B\) con vật đến dự tiệc.

Giữa những con chó và mèo có \(N\) nhóm bạn thân. Nhóm thứ \(i\) gồm tất cả \(Q_i-P_i+1\) con chó có số hiệu từ \(P_i\) đến \(Q_i\) và tất cả \(S_i-R_i+1\) con mèo có số hiệu từ \(R_i\) đến \(S_i\). Nhóm này có độ thân thiết là số nguyên dương \(T_i\). Một con vật có thể thuộc nhiều nhóm hoặc không thuộc nhóm nào.

Bạn rất thân với con chó số \(C\) và đã mời thành công con chó đó. Bạn sẽ lặp lại quy trình sau để mời những con vật còn lại:

1. Nếu đã mời thành công cả \(A+B\) con vật thì kết thúc.
2. Tính giá trị hạnh phúc khi mời từng con vật chưa được mời. Xét các nhóm mà con vật đó thuộc về và đã có ít nhất một con chó hoặc mèo được mời thành công. Giá trị hạnh phúc là độ thân thiết lớn nhất trong các nhóm như vậy. Nếu không có nhóm nào thỏa mãn, giá trị hạnh phúc bằng \(0\).
3. Chọn con vật có giá trị hạnh phúc lớn nhất. Nếu có nhiều con như vậy, ưu tiên chó hơn mèo; nếu vẫn còn nhiều lựa chọn, ưu tiên con có số hiệu nhỏ hơn.
4. Nếu giá trị hạnh phúc của con vật được chọn bằng \(0\), việc mời thất bại và quy trình kết thúc. Ngược lại, bạn mời thành công con vật đó rồi tiếp tục quy trình.

Yêu cầu

Cho \(A\), \(B\), \(C\) và thông tin của \(N\) nhóm bạn thân, hãy xác định liệu có mời thành công tất cả các con vật hay không. Nếu có, hãy tính tổng giá trị hạnh phúc của những con vật được chọn qua các bước của quy trình. Con chó số \(C\) đã được mời từ trước nên không đóng góp vào tổng này.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(A\), \(B\), \(C\), lần lượt là số con chó, số con mèo và số hiệu con chó đã được mời.
• Dòng thứ hai chứa số nguyên \(N\), là số nhóm bạn thân.
• Dòng thứ \(i+2\) (\(1 \le i \le N\)) chứa năm số nguyên \(P_i\), \(Q_i\), \(R_i\), \(S_i\), \(T_i\), cách nhau bởi dấu cách, mô tả nhóm thứ \(i\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên:

• Nếu mời thành công cả \(A+B\) con vật, in tổng giá trị hạnh phúc của các con vật được chọn qua các bước của quy trình.
• Nếu việc mời thất bại giữa chừng, in \(-1\).

Ràng buộc

• \(1 \le A \le 1\,000\,000\,000\).
• \(1 \le B \le 1\,000\,000\,000\).
• \(1 \le C \le A\).
• \(1 \le N \le 100\,000\).
• \(1 \le P_i \le Q_i \le A\) với mọi \(1 \le i \le N\).
• \(1 \le R_i \le S_i \le B\) với mọi \(1 \le i \le N\).
• \(1 \le T_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Các bộ kiểm thử chiếm \(30\%\) tổng số điểm thỏa mãn \(A \le 1\,000\), \(B \le 1\,000\) và \(N \le 2\,000\).
• Các bộ kiểm thử chiếm \(50\%\) tổng số điểm thỏa mãn \(N \le 2\,000\).

Các tỉ lệ trên là các điều kiện tích lũy; không cộng chúng thành các nhóm điểm độc lập.

Ví dụ

5 6 3
4
2 4 1 3 20
1 2 2 4 40
4 5 2 3 30
4 4 4 6 10

280

10 10 1
2
1 5 1 5 3
6 10 6 10 4

-1