AT_abc424_g [ABC424G] Set list

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ C_1 $ $ B_2 $ $ C_2 $ $ \vdots $ $ B_M $ $ C_M $

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

### Sample Explanation 1 例えば、曲 $ 1,3 $ を選んで次のように踊るアイドルを選ぶことができます。 - 曲 $ 1 $ では、アイドル $ 3 $ のみが踊る。 - 曲 $ 3 $ では、アイドル $ 1,2,3 $ が踊る。 このとき、アイドル $ 1,2,3 $ が踊る曲数はそれぞれ $ 1,1,2 $ であり、条件をみたしています。 このとき、選んだ曲の盛り上がりの総和は $ 1+10=11 $ となります。 条件をみたしつつこれより盛り上がりの総和が大きくなるように曲を選ぶことはできないため、 $ 11 $ を出力します。 ### Sample Explanation 2 例えば、曲 $ 1,2,3,4,5 $ を選んで、次のように踊るアイドルを選ぶことができます。 - 曲 $ 1 $ では、誰も踊らない。 - 曲 $ 2 $ では、誰も踊らない。 - 曲 $ 3 $ では、アイドル $ 1 $ のみが踊る。 - 曲 $ 4 $ では、アイドル $ 1 $ のみが踊る。 - 曲 $ 5 $ では、アイドル $ 1 $ のみが踊る。 このとき選んだ曲の盛り上がりの総和は $ 5000000000 $ となり、これが最大となります。 ### 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 $ - 入力はすべて整数