As a good friend of Muntasir, Evan was finding a way to help him bear the cost of his mother’s treatment. So today, he has opened a charity bag shop.
Now, he has bags to sell. You are given an array of integers, where is the size of the -th bag. He has somehow managed to know that there will be exactly customers today and the -th of them will search for a bag of size and will donate amount of money if he buys the bag.
But Evan is amazing at convincing people! (just like you when it comes to programming!) As people are not so easy going nowadays, he has already calculated the convincing value ( ) for every -th customer, which means that he will be able to convince the -th customer to buy a bag of size if . He can also ignore any customer whether convincing that customer is possible or not. No customer will buy more than one bag and Evan can't sell a bag twice or more.
What is the maximum amount of money Evan will be able to collect at the end of the day, if he sells bags optimally?
The first line contains a single integer , the number of bags available in the shop.
The second line contains integers - the sizes of each available bag.
The next line contains one integer , the number of customers.
The following lines contain three integers each: the preferred size of the -th customer , the amount of money he will donate if he buys the bag and his convincing value
Output one integer, the maximum amount of money Evan can collect today to help Muntasir.
Input | Output |
---|---|
3 5 10 15 3 5 3 0 7 10 5 19 5 4 | 18 |