CF580D Kefa and Dishes

$\texttt{songshe}$ 进入了一家餐厅，这家餐厅中有 $n\ (1\leqslant n\leqslant18)$ 个菜。$\texttt{songshe}$ 对第 $i$ 个菜的满意度为 $a_i\ (0\leqslant a_i\leqslant10^9)$。 对于这 $n$ 个菜，有 $k\ (0\leqslant k\leqslant n^2-n)$ 条规则：如果 $\texttt{songshe}$ 在吃完第 $x_i$ 个菜之后立刻吃了第 $y_i\ (x_i\neq y_i)$ 个菜，那么会额外获得 $c_i\ (0\leqslant c_i\leqslant10^9)$ 的满意度。 $\texttt{songshe}$ 要吃 $m\ (1\leqslant m\leqslant n)$ 道任意的菜，但是他希望自己吃菜的顺序得到的满意度最大，请你帮 $\texttt{songshe}$ 解决这个问题。

无

无

In the first sample it is best to first eat the second dish, then the first one. Then we get one unit of satisfaction for each dish and plus one more for the rule. In the second test the fitting sequences of choice are 4 2 1 or 2 1 4. In both cases we get satisfaction 7 for dishes and also, if we fulfill rule 1, we get an additional satisfaction 5.