Minceraft

Minceraft is a popular game where players combine items called mince together to form new types of mince. This process of combining mince to create a new type of mince is called rafting. Each raft costs a certain amount of existing minces and creates a new mince item. Rafts can use minces produced by other rafts. Rafts can be used in any order and any number of times as long as there are sufficient amounts of mince of the types required. Given a list of initial minces and rafts find the maximum amount of mince that can be made of the type produced from the last raft in the given list.

Input

The first line contains the number of types of initial minces $M$ ($1 \leq M \leq 50$) and the number of rafts $R$ ($1 \leq R \leq 10^3$).

The second line contains $M$ integers where integer $M_i$ ($1 \leq M_i \leq 10^9$) denotes the amount of mince $i$.

The following $R$ lines each describe a raft. The first integer of each line is $C_j$, denoting the number of types of minces needed in the $j$-th raft ($1 \le j \le R$). Then there is a pair of integers for each mince type in the raft.

• The first integer $T$ ($1 \leq T \lt M + j$) in the pair denotes the type of mince required.
• The second integer $A$ ($1 \leq A \leq 5$) denotes the amount of mince required of this type.

The $j$-th raft produces a mince of type $M + j$. The same mince type will not appear twice in the same raft. Rafts will only use mince types that are strictly less than $M + j$. That is, rafts will only use initial mince types or mince types from previous rafts.

Output

The maximum amount of mince of type $M + R$ that can be made (that is, the type of mince produced from the last raft).

Subtasks

• Subtask 1 (30%): $M = 1$. That is, there is only one initial mince type.
• Subtask 2 (70%): No other constraints apply.

Explanation

In sample case 1 we have 100 units of mince of type 1. Our last and only raft requires 5 units of type 1 to produce 1 unit of type 2 mince. Hence, the maximum amount of type 2 mince that can be made is 20 units.

In sample case 2 our first raft uses 5 units of type 1 mince to make 1 unit of type 3. Our second raft uses 5 units of type 2 mince to make 1 unit of type 4. Our third and final raft uses 1 unit of type 3 and 1 unit of type 4, so to make 1 unit of type 5 mince we need 5 units of type 1 and 5 units of type 2 mince. Hence, the maximum amount of type 5 mince that can be made is 2 units.