Bữa tiệc của Kefa

Kefa đến nhà hàng và được đưa thực đơn gồm $n$ món ăn. Anh muốn gọi đúng $m$ món ăn khác nhau (không gọi lặp lại một món nào).

Món thứ $i$ mang lại cho Kefa $a_i$ đơn vị hài lòng.

Ngoài ra, một số cặp món ăn khi ăn liền kề nhau sẽ tạo cảm giác đặc biệt. Có $k$ quy tắc, mỗi quy tắc gồm ba số $x$, $y$, $c$ với ý nghĩa: nếu Kefa ăn món $x$ ngay trước món $y$ (giữa hai món này không có món nào khác), thì độ hài lòng của anh tăng thêm $c$.

Kefa sẽ ăn $m$ món theo một thứ tự nào đó. Tổng độ hài lòng bằng tổng $a_i$ của các món được chọn cộng với tổng $c$ của mọi quy tắc được thỏa mãn bởi thứ tự ăn. Hãy tìm tổng độ hài lòng lớn nhất mà Kefa có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $k$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_i$, $y_i$, $c_i$ mô tả một quy tắc. Đảm bảo không có hai quy tắc nào trùng cặp $(x_i,y_i)$.

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng độ hài lòng lớn nhất Kefa có thể đạt được.

Ràng buộc

• $1\le m\le n\le 18$
• $0\le k\le n·(n-1)$
• $0\le a_i\le {10}^9$
• $1\le x_i,y_i\le n$, $0\le c_i\le {10}^9$

Ví dụ