P7842 "C.E.L.U-03" Explorer's Notes III.

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.

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.

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}}$.

Only one number, the answer.

### 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 | Testdata ID | $n \le$ | $m \le$ | | :---: | :---: | :---: | | $1$ | $9$ | $10^3$ | | $2$ | $18$ | $10^3$ | | $3 \sim 6$ | $9$ | $10^5$ | | $7 \sim 10$ | $18$ | $10^5$ | 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