← 返回题目列表

Codeforces · 580/D

D. 克法和菜肴

中文机器翻译题面 查看原题

当科法来到餐厅坐到餐桌时,服务员立即给他送来了菜单。有n个菜。 Kefa知道他正好需要m道菜。但此时,他并不想将同一道菜点两次,以尽可能多地品尝菜肴。

Kefa 知道第 i 道菜给他带来了 a 个单位的满意度。但有些菜不适合搭配,有些菜则搭配得很好。 Kefa给自己设定了k条吃以下类型食物的规则——如果他恰好在y菜之前吃x菜(x和y之间不应该有其他菜),那么他的满意度会提高c。

当然,我们的鹦鹉希望通过去餐厅获得最大可能的满足感。帮助他完成这项艰巨的任务!

输入

输入的第一行包含三个空格分隔的数字,n、m 和 k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n * (n - 1)) — 菜单上的菜肴数量、Kefa 需要吃多少份才能吃饱以及饮食规则数量。

第二行包含 n 个空格分隔的数字 ai,(0 ≤ ai ≤ 109) — 他从第 i 道菜中获得的满足感。

接下来的 k 行包含规则。第 i 条规则由三个数字 xi、yi 和 ci 描述(1 ≤ xi、yi ≤ n、0 ≤ ci ≤ 109)。这意味着如果你在 yi 道菜之前吃 xi 菜,那么 Kefa 的满意度会增加 ci。保证不存在这样的索引对 i 和 j (1 ≤ i < j ≤ k),即 xi = xj 和 yi = yj。

输出

在输出的单行中打印 Kefa 从去餐厅获得的最大满意度。

示例

输入 #1

2 2 1
1 1
2 1 1

输出 #1

3

输入 #2

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

输出 #2

12

注意

在第一个样本中,最好先吃第二道菜,然后再吃第一道菜。然后我们为每道菜获得一个满意单位,并为规则再加上一个满意单位。

在第二个测试中,选择的拟合序列是 4 2 1 或 2 1 4。在这两种情况下,我们对菜肴的满意度为 7,而且,如果我们满足规则 1,我们会获得额外的满意度 5。