Problem Statement

There is a group of $N$ idols: idol $1$, idol $2$, $\ldots$, idol $N$. There are $M$ candidate songs, numbered song $1$, song $2$, $\ldots$, song $M$. Takahashi wants to select some of these songs (possibly $0$) and hold a live performance. However, the same song can be selected at most once.

Idol $i$ $(1\leq i\leq N)$ can dance up to $A_i$ songs. In the live performance, song $j$ $(1\leq j\leq M)$ requires $B_j$ idols to dance, and (regardless of who dances) the excitement of that song is $C_j$.

Takahashi selects the songs to be performed and, for each selected song, the idols who will dance, without exceeding each idol’s allowed number of dances. Find the maximum possible sum of excitement of the selected songs.

Constraints

• $1\leq N\leq 100$
• $1\leq M\leq 100$
• $0\leq A_i\leq M$
• $0\leq B_i\leq N$
• $0\leq C_i\leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
B_1 C_1
B_2 C_2
\vdots
B_M C_M

Output

Output the maximum possible sum of excitement of the songs that Takahashi selects.