AT_abc448_b [ABC448B] Pepper Addiction

高橋君はコショウが大好きです。 $ M $ 種類のコショウがレストランに置いてあり、それぞれを種類 $ 1,2,\dots,M $ と呼びます。 このレストランに種類 $ j $ ( $ 1 \le j \le M $ ) のコショウは $ C_j $ g だけあります。 高橋君はこの店で $ N $ 個の料理を注文しました。 相性の都合で $ i $ ( $ 1 \le i \le N $ ) 番目の料理には種類 $ A_i $ のコショウしかかけることができず、 $ i $ 番目の料理にかけられるコショウの量の上限は $ B_i $ g です。 また、高橋君がこれらの料理にかけられるのはレストランに置いてあるコショウのみです。つまり、種類 $ j $ のコショウを合計 $ C_j $ g を超えてかけることはできません。 高橋君は、料理にかけたコショウの量の合計を最大にするようにどの料理にどれだけのコショウをかけるかを決めます。 このとき、高橋君は合計何 g のコショウを料理にかけることができますか？

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

答えを整数として出力せよ。

### Sample Explanation 1 この入力では $ 5 $ 種類のコショウがあり、種類 $ 1,2,3,4,5 $ のコショウがそれぞれ $ 4,4,8,3,7 $ g あります。 以下のようにすると料理にかけたコショウの量の合計が $ 15 $ g となり、これが達成可能な最大です。 - $ 1 $ 番目の料理に種類 $ 1 $ のコショウを $ 2 $ g かける。 - $ 2 $ 番目の料理にはコショウをかけない。 - $ 3 $ 番目の料理に種類 $ 5 $ のコショウを $ 2 $ g かける。 - $ 4 $ 番目の料理に種類 $ 4 $ のコショウを $ 3 $ g かける。 - $ 5 $ 番目の料理に種類 $ 2 $ のコショウを $ 1 $ g かける。 - $ 6 $ 番目の料理に種類 $ 5 $ のコショウを $ 4 $ g かける。 - $ 7 $ 番目の料理に種類 $ 2 $ のコショウを $ 3 $ g かける。 ### Constraints - 入力は全て整数 - $ 1 \le N,M \le 1000 $ - $ 1 \le A_i \le M $ - $ 1 \le B_i,C_i \le 10^6 $