import java.util.*;\npublic class Main {\n static long[] a; \n static long[][] c; \n static long[][] dp; \n static long res; \n static ArrayList sta; \n \n public static void main(String[] args) { \n Scanner sc = new Scanner(System.in); \n int n = sc.nextInt(); \n int m = sc.nextInt(); \n int k = sc.nextInt(); \n \n a = new long[n]; \n c = new long[n][n]; \n dp = new long[1<<18][n]; \n res = 0; \n sta = new ArrayList(); \n \n for (int i = 0; i < n; i++) { \n a[i] = sc.nextLong(); \n } \n \n for (int i = 0; i < k; i++) { \n int x = sc.nextInt(); \n int y = sc.nextInt(); \n int z = sc.nextInt(); \n c[x-1][y-1] = z; \n } \n \n for (int i = 0; i < n; i++) { \n Arrays.fill(dp[i], -10000000000L); \n } \n \n for (int i = 0; i < n; i++) { \n dp[0][i] = 0; \n dp[1<<i][i] = a[i]; \n } \n \n for (int i = 1; i < (1<<n); i++) { \n if (count(i) == m) { \n sta.add(i); \n } \n for (int j = 0; j < n; j++) { \n if ((i & (1<<j)) == 0) { \n for (int k = 0; k < n; k++) { \n if ((i & (1<<k)) != 0) { \n dp[i|(1<<j)][j] = Math.max(dp[i|(1<<j)][j], dp[i][k]+a[j]+c[k][j]); \n } \n } \n } \n } \n } \n \n int sz = sta.size(); \n for (int i = 0; i < n; i++) { \n for (int j = 0; j < sz; j++) { \n res = Math.max(res, dp[sta.get(j)][i]); \n } \n } \n \n System.out.println(res); \n } \n \n public static int count(int x) { \n int s = 0; \n while (x != 0) { \n if ((x & 1) != 0) { \n s++; \n } \n x >>= 1; \n } \n return s; \n } \n}
