Optimal Course Selection

After the final exams, the annual course selection period begins. Little C has set a personal goal: to accumulate at least \(T\) credits in the new semester. According to the announcement from the academic affairs office, there are \(m\) categories available. In the \(i\)th category, there are \(n_i\) courses. In addition to the overall requirement of earning at least \(T\) credits, Little C further sets the requirement that in the \(i\)th category (for \(i=1,2,\dots,m\)) he must earn at least \(s_i\) credits.

Every course gives a certain number of credits and requires a certain amount of brainpower (cost). Moreover, some pairs of courses have special relationships:

• If two similar courses are taken simultaneously, the brainpower cost may be reduced (synergy bonus).
• If two very hardcore courses are taken simultaneously, the brainpower cost may increase (penalty).
• If two courses have a time conflict, they cannot be taken together.

Help Little C choose a set of courses such that all the credit requirements are met and the total brainpower cost is minimized. The total cost is calculated as the sum of the individual course costs plus adjustments due to relationships. For a bonus relationship (type 1) the cost is reduced by \(\delta\); for a penalty relationship (type 2) it is increased by \(\delta\); and for a conflict (type 0) the two courses cannot be selected simultaneously.

inputFormat

The first line contains three integers: \(T\), \(m\) and \(r\), where \(T\) is the overall minimum required credits, \(m\) is the number of categories, and \(r\) is the number of relationships.

The second line contains \(m\) integers: \(s_1, s_2, \dots, s_m\), where \(s_i\) is the minimum required credits for the \(i\)th category.

Then for each category \(i\) (from 1 to \(m\)):

• A line containing the integer \(n_i\), the number of courses in category \(i\).
• Followed by \(n_i\) lines, each containing two integers: the credit value and the brainpower cost of that course.

Finally, there are \(r\) lines, each describing a relationship with 6 integers: a b c d type delta . Here, a and c (1-indexed) represent the category numbers; b and d (1-indexed) represent the course indices within their respective categories; type indicates the relationship type (0 for conflict, 1 for bonus, 2 for penalty); and delta is the cost adjustment value (for bonus, subtract \(\delta\); for penalty, add \(\delta\); for conflict, the courses cannot be taken together).

outputFormat

Output a single integer representing the minimum total brainpower cost needed to achieve all credit requirements. If it is impossible to meet the requirements, output -1.

sample

6 2 3
2 3
2
3 5
2 3
2
4 6
2 2
1 1 2 1 0 0
1 2 2 2 1 1
1 1 2 2 2 2

9