U181894 选课

新学期开始了, 又到了小Y最喜欢的选课时间!同一门课在一星期内可能会有多节, 如果两门课的某一节课在同一个时间点上, 那么这两门课就不能同时选, 称为"课程冲突"。此外，每门课都有不同的学分。好学的小Y想在课程不冲突的情况下，使选的课的学分总和尽可能大，请你帮小Y计算一下他这学期最多能修多少学分。

第一行, 一个整数$n$,表示这学期开的课程数量。 第二行, $n$个整数$s_1,s_2,...s_n$, 依次表示课程$1, 2, ...,n$的学分。 接下来若干行, 每行$3$个整数$i, d, t,$ 表示课程$i$在星期$d$的第$t$节有一节课。(**不保证数据不会重复**)

一行一个整数, 表示答案。

$1\leq n \leq 30$ $1\leq d \leq 5$ $1\leq t \leq 6$ $1\leq s_i \leq 10$ **样例解释** 课程$1$在星期一和星期三的第$1$节有课, 课程$2$在星期二和星期五的第$2$节有课, 课程$3$在星期一的第$1$节,星期二的第$3$节,星期五的第$2$节有课。在不冲突的前提下, 只选择课程$3$时学分总和最大, 为$6$学分, 因此你应该输出$6$。