Description

The remade Explorer's Notes consists of $n$ levels. Each level has a difficulty $b_i$. There are also $m$ achievements. The $i$-th achievement requires you to complete exactly $sum_i$ levels, and they must be exactly $a_{i_1}, a_{i_2}, ..., a_{i_{sum_i}}$. Completing the $i$-th achievement gives you a score of $v_i$.
If you push levels for a long time without getting any achievement, Xiao Soup will feel tired. Also, achievements must be unlocked in a certain order. Therefore, if the last obtained achievement is the $i$-th one, then the condition to obtain the $j$-th achievement next is: $i < j$ and $w+\sum\limits_{k=1}^{sum_i} b_{a_{i_k}} \ge \sum\limits_{k=1}^{sum_j} b_{a_{j_k}}$, where $w$ is a given constant.
There are no restrictions for obtaining the first achievement. Find the maximum total score he can get.

Input Format

The first line contains three numbers $n, m, w$.
The second line contains $n$ numbers $b_i$.
The next $m$ lines describe the achievements. In the $i$-th line, the first two numbers are $v_i, sum_i$, followed by $sum_i$ numbers $a_{i_1}, a_{i_2}, ..., a_{i_{sum_i}}$.

Output Format

Only one number, the answer.

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

Hint

Sample Explanation

Sample Explanation 1
Complete achievements $1, 2$ in order.

Sample Explanation 2
Complete achievements $4, 5, 6$ in order. Note that the restriction between achievements only takes effect between two adjacent obtained achievements.

Constraints

For $100\%$ of the testdata: $1 \le n \le 18$, $1 \le m \le 10^5$, $1 \le sum_i \le 18$, $1 \le w, b_i, v_i \le 10^3$, $1 \le a_i \le n$.

Translated by ChatGPT 5