Background

After clearing the game Explorer's Notes made by Xiao Soup, Luo Si Ji felt very sad. To ease the pain in his heart, he decided to remake Explorer's Notes and turn it into a happy game.
After some time, Luo Si Ji finished it and called Xiao Soup to test it.

Problem 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