Revamped Explorer's Notes

The game has been redesigned into a series of \( n \) levels, each with a difficulty value \( b_i \). There are also \( m \) achievements. The \( i \)-th achievement requires you to complete exactly \( r_i \) levels, which are exactly \( a_{i_1}, a_{i_2}, \ldots, a_{i_{r_i}} \), and will award you \( v_i \) points.

However, if you progress through the levels for too long without earning any achievement, our protagonist, Soup, will feel fatigued. Moreover, achievements must be unlocked in a specific order. In particular, if you have just unlocked the \( i \)-th achievement and you wish to unlock the \( j \)-th achievement next (with \( i < j \)), the following condition must hold: \[ w + \sum_{k=1}^{r_i} b_{a_{i_k}} \ge \sum_{k=1}^{r_j} b_{a_{j_k}}, \] where \( w \) is a given constant. The first achievement you unlock has no such restriction.

Your task is to determine the maximum total score Soup can obtain by choosing a valid sequence of achievements.

inputFormat

The input consists of several lines:

1. The first line contains three integers \( n \), \( m \), and \( w \) representing the number of levels, the number of achievements, and the constant \( w \) respectively.
2. The second line contains \( n \) integers: \( b_1, b_2, \ldots, b_n \) where \( b_i \) is the difficulty of the \( i \)-th level.
3. Then \( m \) lines follow, each describing an achievement. Each achievement line is formatted as follows:
   r a1 a2 ... ar v
   Here, \( r \) (denoted as \( r_i \) in the description) is the number of levels required for the achievement, \( a_1, a_2, \ldots, a_r \) are the indices of those levels, and \( v \) is the score you obtain by unlocking that achievement.

outputFormat

Output a single integer: the maximum total score that can be obtained by unlocking a valid sequence of achievements.

sample

5 3 3
2 3 1 5 4
2 1 3 10
3 2 4 5 15
1 4 7

22