AT_abc424_g [ABC424G] Set list

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.

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 the maximum possible sum of excitement of the songs that Takahashi selects.

### Sample Explanation 1 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 Explanation 2 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. ### 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.