G - Set list Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 625 点

問題文

アイドル 1, アイドル 2, \ldots, アイドル N の N 人のアイドルからなるグループがあります。
また、曲の候補が M 曲あり、それぞれ曲 1, 曲 2, \ldots, 曲 M と番号づけられています。
高橋君は、これらのうちから何曲か（0 曲でも良い）を選びライブを行いたいと考えています。
ただし、同じ曲は 1 回までしか選ぶことはできません。

アイドル i (1\leq i\leq N) は A_i 曲まで踊ることができます。
また、ライブにおいて、曲 j (1\leq j\leq M) では B_j 人のアイドルが踊る必要があり、（誰が踊ったかによらず）その曲の盛り上がりは C_j です。

高橋君は、それぞれのアイドルが踊れる回数を超えないように、 ライブで演奏する曲およびそれぞれの曲で踊るアイドルを選びます。 選んだ曲の盛り上がりの総和としてあり得る最大値を求めてください。

制約

  • 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
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

高橋君が選んだ曲の盛り上がりの総和としてあり得る最大値を出力せよ。

入力例 1

3 3
1 1 3
1 1
2 5
3 10

出力例 1

11

例えば、曲 1,3 を選んで次のように踊るアイドルを選ぶことができます。

  • 曲 1 では、アイドル 3 のみが踊る。
  • 曲 3 では、アイドル 1,2,3 が踊る。

このとき、アイドル 1,2,3 が踊る曲数はそれぞれ 1,1,2 であり、条件をみたしています。
このとき、選んだ曲の盛り上がりの総和は 1+10=11 となります。

条件をみたしつつこれより盛り上がりの総和が大きくなるように曲を選ぶことはできないため、 11 を出力します。

入力例 2

2 6
6 0
0 1000000000
0 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1000000000

出力例 2

5000000000

例えば、曲 1,2,3,4,5 を選んで、次のように踊るアイドルを選ぶことができます。

  • 曲 1 では、誰も踊らない。
  • 曲 2 では、誰も踊らない。
  • 曲 3 では、アイドル 1 のみが踊る。
  • 曲 4 では、アイドル 1 のみが踊る。
  • 曲 5 では、アイドル 1 のみが踊る。

このとき選んだ曲の盛り上がりの総和は 5000000000 となり、これが最大となります。

Score : 625 points

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.

Sample Input 1

3 3
1 1 3
1 1
2 5
3 10

Sample Output 1

11

For example, he can select songs 1,3 and choose the dancers as follows.

  • In song 1, only idol 3 dances.
  • In song 3, idols 1,2,3 dance.

Then, the numbers of songs danced by idols 1,2,3 are 1,1,2, respectively, and the conditions are satisfied. Here, the sum of excitement of the selected songs is 1+10=11.

It is impossible to select songs so that the sum of excitement becomes larger while satisfying the conditions, so output 11.

Sample Input 2

2 6
6 0
0 1000000000
0 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1000000000

Sample Output 2

5000000000

For example, he can select songs 1,2,3,4,5 and choose the dancers as follows.

  • In song 1, nobody dances.
  • In song 2, nobody dances.
  • In song 3, only idol 1 dances.
  • In song 4, only idol 1 dances.
  • In song 5, only idol 1 dances.

Then, the sum of excitement of the selected songs is 5000000000, and this is maximum.