D. Кефа и блюда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда Кефа пришел в ресторан и уселся за столик, официант сразу же принес ему меню. Там оказалось целых n блюд. Кефа знает, что ему нужно ровно m порций, чтобы насытиться. Но при этом он не хочет заказывать одно и то же дважды, чтобы попробовать максимальное количество блюд.

Кефа знает, что i-е блюдо поднимет его удовлетворенность на ai. Но некоторые блюда плохо сочетаются друг с другом, а некоторые — наоборот хорошо. Кефа установил себе k правил поедания пищи следующего вида — если блюдо x съесть непосредственно перед блюдом y (т. е. между x и y не должно быть других блюд), то удовлетворенность Кефы увеличится на c.

Конечно же наш попугай хочет получить максимально возможную удовлетворенность от похода в ресторан. Помогите ему в этом непростом деле!

Входные данные

Первая строка входного файла содержит три числа, разделенные пробелами, n, m и k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n * (n - 1)) — количество блюд в меню, количество порций, которое нужно съесть Кефе, чтобы насытиться, и количество правил поедания пищи.

Во второй строке находятся n чисел ai, разделенные пробелами (0 ≤ ai ≤ 109) — удовлетворенность, получаемая от i-го блюда.

В следующих k строках находятся правила. i-е правило описывается тремя числами xi, yi и ci (1 ≤ xi, yi ≤ n, 0 ≤ ci ≤ 109). Это значит, что если блюдо xi съесть непосредственно перед блюдом yi, то удовлетворенность Кефы увеличится на ci. Гарантируется, что нет таких пар индексов i и j (1 ≤ i < j ≤ k), что xi = xj и yi = yj.

Выходные данные

В единственной строке выходного файла выведите максимальную удовлетворенность, которую Кефа может получить от похода в ресторан.

Примеры
Входные данные
2 2 1
1 1
2 1 1
Выходные данные
3
Входные данные
4 3 2
1 2 3 4
2 1 5
3 4 2
Выходные данные
12
Примечание

В первом тесте лучше всего съесть сначала второе блюдо, а потом первое. Тогда мы получим по единице удовлетворенности за каждое блюдо и еще единицу за правило.

Во втором тесте подходят последовательности выбора 4 2 1 или 2 1 4. В обоих случаях мы получим удовлетворенность 7 за отдельные блюда, а также, выполнив правило 1, получаем еще дополнительную удовлетворенность 5.