Đề bài

Khi Hoàng đến nhà hàng và ngồi vào bàn, người phục vụ lập tức mang thực đơn đến cho anh. Trên thực đơn có n món ăn. Hoàng biết rằng anh cần gọi chính xác m món để ăn no. Tuy nhiên, anh không muốn gọi cùng một món hai lần để có thể thưởng thức được nhiều món khác nhau.

Mỗi món ăn thứ i mang lại cho Hoàng a_i đơn vị độ hài lòng. Ngoài ra, một số món ăn khi ăn liền kề nhau sẽ mang lại hiệu ứng đặc biệt: có thể tăng thêm độ hài lòng. Hoàng đã đặt ra k quy tắc kiểu này, nếu anh ăn món x ngay trước món y (không có món nào khác xen giữa x và y), thì độ hài lòng sẽ tăng thêm c.

Hoàng muốn có được độ hài lòng tối đa từ bữa ăn của mình. Hãy giúp anh ấy tìm ra lựa chọn tốt nhất.

Input
Dòng đầu tiên chứa ba số nguyên n, m và k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n × (n - 1)) tương ứng với số lượng món ăn trong thực đơn, số món Hoàng cần gọi và số lượng quy tắc tăng thêm độ hài lòng.
Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (0 ≤ a_i ≤ 10⁹) là độ hài lòng mà Hoàng nhận được khi ăn món thứ i.
Tiếp theo là k dòng, mỗi dòng chứa ba số nguyên x_i, y_i và c_i (1 ≤ x_i, y_i ≤ n, 0 ≤ c_i ≤ 10⁹). Điều này có nghĩa là nếu ăn món x_i ngay trước món y_i, độ hài lòng sẽ tăng thêm c_i. Đảm bảo không có hai quy tắc nào trùng nhau.

Output
In ra một số nguyên duy nhất là độ hài lòng tối đa mà Hoàng có thể nhận được.

Sample input

2 2 1
1 1
2 1 1

sample ouput

3

Sample input

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

Sample ouput

12

Note

Trong mẫu đầu tiên, tốt nhất là ăn món thứ hai trước, sau đó là món thứ nhất. Sau đó, chúng ta nhận được một đơn vị hài lòng cho mỗi món ăn và cộng thêm một đơn vị cho quy tắc.

Trong bài kiểm tra thứ hai, các chuỗi lựa chọn phù hợp là 4 2 1 hoặc 2 1 4. Trong cả hai trường hợp, chúng ta nhận được mức độ hài lòng 7 cho các món ăn và cũng, nếu chúng ta thực hiện quy tắc 1, chúng ta nhận được thêm mức độ hài lòng 5.