JOI-kun chụp một bức ảnh phong cảnh ban đêm. Bức ảnh gồm \(N \times N\) điểm ảnh, tức là có \(N\) điểm ảnh theo mỗi chiều ngang và dọc. Điểm ảnh ở cột thứ \(x\) từ trái sang và hàng thứ \(y\) từ dưới lên (\(1 \le x,y \le N\)) được gọi là điểm ảnh \((x,y)\).

Mỗi điểm ảnh thể hiện một tòa nhà, bầu trời đêm hoặc ngôi sao, lần lượt có màu trắng, đen hoặc vàng. Với mỗi \(1 \le i \le N\), trong cột thứ \(i\), các điểm ảnh từ hàng dưới cùng đến hàng thứ \(A_i\) từ dưới lên đều có màu trắng, thể hiện các tòa nhà. Có \(M\) điểm ảnh màu vàng thể hiện các ngôi sao; điểm ảnh vàng thứ \(j\) (\(1 \le j \le M\)) ở vị trí \((X_j,Y_j)\). Tất cả điểm ảnh còn lại đều màu đen, thể hiện bầu trời đêm.

Một vùng hình chữ nhật trong ảnh được gọi là thể hiện một chòm sao nếu thỏa mãn cả hai điều kiện:

• Không có điểm ảnh màu trắng trong vùng đó.
• Có ít nhất hai điểm ảnh màu vàng trong vùng đó.

JOI-kun đã chán ngắm các chòm sao. Cậu muốn tô đen một số điểm ảnh vàng sao cho không còn vùng hình chữ nhật nào thể hiện một chòm sao. Tuy nhiên, tô đen nhiều điểm ảnh vàng sẽ khiến bức ảnh mất tự nhiên. Cụ thể, nếu tô đen điểm ảnh vàng thứ \(j\), mức độ thiếu tự nhiên của ảnh tăng thêm \(C_j\). Ban đầu, mức độ thiếu tự nhiên bằng \(0\).

Cho thông tin bức ảnh và chi phí tô đen từng điểm ảnh vàng, hãy tính mức độ thiếu tự nhiên nhỏ nhất có thể sau khi tô sao cho không còn vùng hình chữ nhật nào thể hiện một chòm sao.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Tất cả giá trị đều là số nguyên, theo định dạng:

N
A_1 ... A_N
M
X_1 Y_1 C_1
...
X_M Y_M C_M

Dữ liệu ra

In ra một dòng chứa mức độ thiếu tự nhiên nhỏ nhất sau khi tô đen một số điểm ảnh vàng để không còn vùng hình chữ nhật nào thể hiện một chòm sao.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le N\) với \(1 \le i \le N\).
• \(1 \le M \le 200\,000\).
• \(1 \le X_j,Y_j \le N\) với \(1 \le j \le M\).
• \(1 \le C_j \le 1\,000\,000\,000\) với \(1 \le j \le M\).
• \(A_{X_j}<Y_j\) với \(1 \le j \le M\).
• \((X_j,Y_j)\ne(X_k,Y_k)\) với \(1 \le j<k \le M\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(14\) điểm: \(N \le 300\), \(M \le 300\)
2. \(21\) điểm: \(N \le 2000\), \(M \le 2000\)
3. \(65\) điểm: Không có

Ví dụ

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

2

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

16

8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13

44

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 3. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.