Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P175SUMI - ROUND 5I - Sức mạnh tối đa

Sau mỗi trận chiến Luffy đều ăn rất nhiều để bù đắp lại phần sức mạnh mà mình đã tiêu hao. Có tất cả N món ăn, mỗi món ăn có giá trị sức mạnh là a[i], Luffy chỉ cần ăn đúng M món ăn là được nhưng sẽ có K cách ăn để tăng được nhiều sức mạnh hơn. Giả sử nếu ăn món thứ y ngay sau món x thì sẽ được tăng thêm w đơn vị sức mạnh.

Hãy giúp Luffy đạt được sức mạnh tối đa sau khi ăn đúng M món.

Input

Dòng đầu gồm 3 số N,M,K

1<=N,M<=18,0<=K<=N*(N-1)

Dòng tiếp theo gồm N số a[i] (0<=a[i]<=10^9)

K dòng tiếp theo mỗi dòng gồm 2 số x,y,w (1<=x,y<=18, 0<=w<=10^9)

x,y,w có nghĩa là nếu ăn món y ngay sau món x sẽ được tăng thêm w sức mạnh.

Output

Kết quả lớn nhất tìm được.

Example

Test 1:
Input:
2 2 1
1 1
2 1 5
Output: 7
Test 2:
Input:
4 3 2
1 2 3 4
2 1 5
3 4 2
Output:
12

Được gửi lên bởi:adm
Ngày:2017-08-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.