Maximize Gem Value Under Sequential Door Deadlines

A thief enters a storage room through door \(0\) and starts a timer. There are \(n\) rooms connected by doors numbered from \(0\) to \(n-1\). Each door \(i\) has a closing time \(d_i\) (measured from the start of the timer), and the thief must exit each door strictly before its closing time (i.e. if the cumulative time upon leaving a room is \(T\), then it must satisfy \(T < d_i\) for the corresponding door).

Each room \(i\) contains an unlimited number of gem types. For each gem type available in room \(i\), you are given its value and the time cost needed to pick one gem. Since the time spent moving between rooms is negligible, the thief may spend some time in each room collecting gems. In room \(i\), if the thief spends \(t_i\) time (an integer amount) collecting gems, he can choose any combination (with repetition) of the gem types available in that room, subject to the time cost. The gain in that room is the maximum total value the thief can obtain by spending exactly \(t_i\) time (calculated via an unbounded knapsack strategy for that room).

The thief visits the rooms in order (\(0, 1, \ldots, n-1\)). Let \(T_0 = t_0\) and \(T_i = t_0+t_1+\cdots+t_i\) for \(i \ge 1\). The constraint for each room \(i\) is that the cumulative time upon leaving must satisfy \(T_i < d_i\). Assuming that the thief can successfully escape from the last room, what is the maximum total value of gems he can collect?

Input/Output: See below for details.

inputFormat

The input begins with an integer \(n\) indicating the number of rooms.

The second line contains \(n\) space‐separated integers \(d_0, d_1, \ldots, d_{n-1}\), where \(d_i\) is the closing time of door \(i\). It is guaranteed that the thief must exit room \(i\) (after spending some time there) strictly before \(d_i\).

Then, for each room \(i\) (from \(0\) to \(n-1\)), the input contains an integer \(k\) denoting the number of gem types in that room. This is followed by \(k\) lines, each containing two integers: value and time, representing the value of the gem and the time required to pick that gem, respectively.

Note: You may assume that the quantity of each gem is unlimited and that all time values are integers.

outputFormat

Output a single integer representing the maximum total value of gems the thief can collect while ensuring he exits each room before the respective door closes.

sample

3
5 10 14
2
3 1
5 3
1
4 2
2
2 1
10 5

30