AT_abc448_b [ABC448B] Pepper Addiction

Takahashi loves pepper. A restaurant has $ M $ types of pepper, called type $ 1,2,\dots,M $ . There are $ C_j $ grams of type $ j $ ( $ 1 \le j \le M $ ) pepper at this restaurant. He ordered $ N $ dishes at this restaurant. Due to compatibility, only type $ A_i $ pepper can be sprinkled on dish $ i $ ( $ 1 \le i \le N $ ), and the upper limit on the amount of pepper that can be sprinkled on dish $ i $ is $ B_i $ grams. Also, he can only use the pepper available at the restaurant. That is, the total amount of type $ j $ pepper sprinkled cannot exceed $ C_j $ grams. He decides how much pepper to sprinkle on each dish to maximize the total amount of pepper sprinkled on the dishes. How many grams of pepper in total can he sprinkle on the dishes?

The input is given from Standard Input in the following format: > $ N $ $ M $ $ C_1 $ $ C_2 $ $ \dots $ $ C_M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

Output the answer as an integer.

### Sample Explanation 1 In this input, there are five types of pepper, with $ 4,4,8,3,7 $ grams of type $ 1,2,3,4,5 $ pepper respectively. The following gives a total of $ 15 $ grams of pepper sprinkled on the dishes, which is the maximum achievable. - Sprinkle $ 2 $ grams of type $ 1 $ pepper on dish $ 1 $ . - Sprinkle no pepper on dish $ 2 $ . - Sprinkle $ 2 $ grams of type $ 5 $ pepper on dish $ 3 $ . - Sprinkle $ 3 $ grams of type $ 4 $ pepper on dish $ 4 $ . - Sprinkle $ 1 $ gram of type $ 2 $ pepper on dish $ 5 $ . - Sprinkle $ 4 $ grams of type $ 5 $ pepper on dish $ 6 $ . - Sprinkle $ 3 $ grams of type $ 2 $ pepper on dish $ 7 $ . ### Constraints - All input values are integers. - $ 1 \le N,M \le 1000 $ - $ 1 \le A_i \le M $ - $ 1 \le B_i,C_i \le 10^6 $