Chọn Dự Án Trên Đồ Thị

Có một đồ thị vô hướng đơn. Chọn một số cạnh làm dự án; để chọn cạnh, phải chọn cả hai đầu của nó. Tổng giá trị bằng tổng trọng số các cạnh đã chọn trừ tổng chi phí của các đỉnh đã chọn. Có thể chọn tập rỗng. Hãy tìm giá trị lớn nhất.

Input

• Dòng đầu chứa $n,m$.
• Dòng thứ hai chứa $a_1,\dots ,a_n$, là chi phí các đỉnh.
• Mỗi trong $m$ dòng tiếp theo chứa $u,v,w$, mô tả một cạnh vô hướng trọng số $w$.

Output

• In một số nguyên: giá trị lớn nhất của đồ thị con.

Constraints

• $1\le n\le 1000$.
• $0\le m\le 1000$.
• $1\le a_i\le 10^9$.
• $1\le w\le 10^9$.
• Không có khuyên hoặc cạnh trùng.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,m\le 18$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

2 1
3 4
1 2 10

3