# 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 $n$ bags to sell. You are given an array $a$ of $n$ integers, where $a_i$ is the size of the $i$-th bag. He has somehow managed to know that there will be exactly $q$ customers today and the $i$-th of them will search for a bag of size $s_i$ and will donate $c_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 ( $x_i$) for every $i$-th customer, which means that he will be able to convince the $i$-th customer to buy a bag of size $p$ if $max(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 ( 1 \leq n \leq 200 )$, the number of bags available in the shop.
The second line contains $n$ integers $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 ( 1 \leq q \leq 200 )$, the number of customers.

The following $q$ lines contain three integers each: the preferred size of the $i$-th customer $s_i ( 1 \leq s_i \leq 10^9 )$, the amount of money $c_i( 1 \leq c_i \leq 10^9 )$ he will donate if he buys the bag and his convincing value $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


### Statistics

42% Solution Ratio

YouKnowWhoEarliest, 1w ago

YouKnowWhoFastest, 0.0s

YouKnowWhoLightest, 524 kB

faria_efaShortest, 1463B