Specimen Leaf Sequencing

In deep autumn, as leaves fall, Augen is delighted along with the children as they collect many golden leaves in the forest. All the collected leaves are regular polygons. Now, Augen plans to make a specimen book for Tong by binding some of these painted leaves.

To create a specimen, one must draw color along the entire boundary of a leaf – with the restriction that no two adjacent edges of the same leaf share the same color. Each specimen (i.e. painted leaf) has an associated beauty value. When binding the specimens into a book, the following ordering conditions must be met:

• The final perimeter (after painting) of the i^th specimen cannot exceed that of the (i+1)^th specimen.
• The beauty value of the i^th specimen cannot exceed that of the (i+1)^th specimen.

Augen has n colored pens. The j^th pen can draw a total length of a_j and can be used to paint at most one leaf. There are m leaves. The i^th leaf is a regular k_i-gon with each side of length b_i, and it has beauty value c_i. A pen can be used to paint a leaf only if the pen’s available drawing length is at least the leaf's perimeter requirement, that is, if

$$k_i \times b_i \le a_j$$

Moreover, once a leaf is painted with a pen, its final perimeter becomes a_j (regardless of its original perimeter). When assembling the specimen book, the sequence of chosen (painted) leaves must obey the following: if the leaf painted using pen p is placed before the one painted using pen q, then it must hold that

$$a_p \le a_q \quad\text{and}\quad c_{(leaf)} \le c_{(leaf')}. $$

Augen wishes to achieve one of the following objectives (the two subproblems are independent):

1. Make as many specimens as possible (i.e. maximize the number of leaves in a valid sequence).
2. Maximize the total beauty of the specimens (i.e. maximize the sum of beauty values of the chosen leaves) under the above ordering conditions.

You are given the data for the pens and the leaves, and an operation flag indicating which objective to optimize.

inputFormat

The input is given in the following format:

 n m
 a1 a2 ... an
 k1 b1 c1
 k2 b2 c2
 ...
 km bm cm
 op

Where:

• n is the number of pens.
• m is the number of leaves.
• The next line contains n integers: a₁, a₂, ..., a_n (the drawing lengths of the pens).
• Each of the next m lines contains three integers: k_i, b_i, c_i, describing the i^th leaf as a regular polygon with k_i sides of length b_i and beauty value c_i. Note that the leaf can only be painted by a pen if k_i * b_i ≤ a_j for that pen.
• op is an integer flag. If op = 1, optimize for the maximum number of specimens. If op = 2, optimize for the maximum total beauty sum.

outputFormat

Output a single integer representing the answer to the chosen subproblem:

• If op = 1, output the maximum number of specimens (leaves) that can be arranged in a valid sequence.
• If op = 2, output the maximum total beauty sum of a valid sequence of specimens.

sample

3 3
10 20 30
3 3 5
4 6 7
3 4 6
1

3