Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Minceraft

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 2.0 seconds

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.

1

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.

2

3

  • Sample Input 1

    1 1
    100
    1 1 5
    

    Sample Output 1

    20
    
  • Sample Input 2

    2 3
    10 20
    1 1 5
    1 2 5
    2 3 1 4 1
    

    Sample Output 2

    2