「C.E.L.U-03」探险者笔记 III

罗司机在通关小 Soup 所制作的游戏《探险者笔记》后，感到十分的悲伤。为了缓解内心的伤痛，他决定改制《探险者笔记》，使其成为一个快乐的游戏。 一段时间之后，罗司机完成了制作，并喊来小 Soup 给他测试。

改制后的《探险者笔记》由 $n$ 个关卡组成，每个关卡有一个难度 $b_i$，同时有 $m$ 个成就，第 $i$ 个成就需要你恰好完成 $sum_i$ 个关卡，且**刚好**分别是 $a_{i_1},a_{i_2},...,a_{i_{sum_i}}$。完成第 $i$ 个成就可以得到 $v_i$ 的分数。 如果长时间推关而没有获得任何成就，小 Soup 会感到疲乏。而且成就的解锁是有一定顺序的。因此上一个获得第 $i$ 个成就接下来再获得第 $j$ 个成就的条件是 $i<j$ 且 $w+\sum\limits_{k=1}^{sum_i}b_{a_{i_k}}\ge\sum\limits_{k=1}^{sum_j}b_{a_{j_k}}$，其中 $w$ 是一个给定的常数。 第一次获得成就没有任何限制。求最多他能得到多少分数。

第一行三个数 $n,m,w$。 第二行 $n$ 个数，$b_i$。 接下来 $m$ 行，第 $i$ 行一开始有两个数，$v_i,sum_i$，接下来会有 $sum_i$ 个数，$a_{i_1},a_{i_2},...,a_{i_{sum_i}}$。

仅一个数，答案。

3 3 1
1 1 2
2 1 1
2 2 1 2
3 2 1 3

4

4 6 2
1 1 3 2
3 3 1 2 3
2 2 2 3
3 3 2 3 4
2 2 1 3
4 3 1 3 4
6 4 1 2 3 4

12

### 样例解释 **样例解释一** 依次完成第 $1,2$ 个成就。 **样例解释二** 依次完成第 $4,5,6$ 个成就。注意，成就之间的限制**只在相邻获得的成就之间生效。** ### 数据范围 |数据编号|$n\leq$|$m\leq$| |:---:|:---:|:---:| |$1$|$9$|$10^3$| |$2$|$18$|$10^3$| |$3\sim 6$|$9$|$10^5$| |$7\sim 10$|$18$|$10^5$| 对于 $100\%$ 的数据 $1\le n\le18,1\le m\le10^5,1\le sum_i\le18,1\le w,b_i,v_i\le10^3,1\le a_i\le n$。