Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Convincing Customers

By faria_efa · Limits 1s, 512 MB

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 nn bags to sell. You are given an array aa of nn integers, where aia_i is the size of the ii-th bag. He has somehow managed to know that there will be exactly qq customers today and the ii-th of them will search for a bag of size sis_i and will donate cic_i 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 ( xix_i) for every ii-th customer, which means that he will be able to convince the ii-th customer to buy a bag of size pp if max(1,sixi)psi+ximax(1, s_i - x_i) \leq p \leq s_i + x_i. 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?

Input

The first line contains a single integer n(1n200)n ( 1 \leq n \leq 200 ), the number of bags available in the shop.
The second line contains nn integers a1,a2,,an(1ai109)a_1, a_2,\dots, a_n ( 1 \leq a_i \leq 10^9 ) - the sizes of each available bag.

The next line contains one integer q(1q200)q ( 1 \leq q \leq 200 ), the number of customers.

The following qq lines contain three integers each: the preferred size of the ii-th customer si(1si109)s_i ( 1 \leq s_i \leq 10^9 ), the amount of money ci(1ci109)c_i( 1 \leq c_i \leq 10^9 ) he will donate if he buys the bag and his convincing value xi(0xi109).x_i ( 0 \leq x_i \leq 10^9 ).

Output

Output one integer, the maximum amount of money Evan can collect today to help Muntasir.

Sample

InputOutput
3
5 10 15
3
5 3 0
7 10 5
19 5 4
18

    Discussion

    Statistics


    42% Solution Ratio

    YouKnowWhoEarliest, 1w ago

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 524 kB

    faria_efaShortest, 1463B

    Submit

    Login to submit

    Related Contests