BOAT

You own a very nice boat. During the summer you receive many requests to rent it, and you want to maximize your profit. For each client you know how many days they want to rent the boat and a list of choices. A choice is an amount of money together with a deadline, where the deadline is a number of days counted from a fixed time origin. You earn the money of a choice only if you can rent the boat to that client, for the requested number of days, so that the rental ends on or before that deadline.

For example, your friend Jack wants to sail the Mediterranean Sea for 20 days and offers the following choices:

• if the deadline is day 60, you earn 1000 EUR, provided the 20-day rental starts between day 0 and day 41 (that is, $60 - 20 + 1$);
• if the deadline is day 70, you earn 800 EUR.

You may drop any client that does not help maximize your profit. However, you must rent the boat to the clients in the order in which they submit their requests. Given all clients and their choices, compute the largest total profit you can obtain.

The program input comes from a text file and contains one or more data sets. Each data set has the following format:

• a line with $n$, the number of clients ($n \le 100$);
• $n$ lines, the $i$-th of which gives the number of days (at most $100$) that client $i$ wants to rent the boat;
• a line with the total number of choices over all clients;
• one line per choice, in the format client_id deadline amount, where client_id is an integer from $1$ to $n$, deadline is at most $100$, and amount is a non-negative integer.

A blank line separates consecutive data sets.

For each data set, print to standard output, on its own line (starting at the beginning of the line), the maximum profit for that data set. A blank line separates the results of different data sets.