Chained Homework Scheduling

You are given a total of $T$ minutes to work on a series of homework assignments. There are $n$ assignments (numbered from 1 to $n$). For the $i$-th assignment, you are given three positive integers: its importance per copy $v_i$, the time required to complete one copy $t_i$, and the number of copies $c_i$. In order to be considered fully completed for an assignment, you must complete all $c_i$ copies; doing so yields a total importance of $$c_i \times v_i.$$ However, you are also allowed to do only a partial number of copies (say $k$ copies with $1\le k< c_i$) of an assignment; in that case you obtain $$k \times v_i$$ importance but you are not allowed to work on any further assignments afterwards. Moreover, if you start an assignment and run out of time before finishing a copy, you gain no importance from that assignment.\n\nThere are also $M$ prerequisite relations. Each relation is described by two different numbers $a$ and $b$, meaning that assignment $a$ is a prerequisite for assignment $b$. Note: An assignment becomes available to work on once any one of its prerequisites is completed. However, once you finish an assignment completely (i.e. doing all $c_i$ copies), if there exists at least one assignment that has it as a prerequisite and there is enough remaining time to do at least one copy of that assignment (i.e. $t_j$ minutes), you are forced to continue your work by starting one of those assignments. In other words, in a valid work plan you form a chain of assignments such that: \n\n1. You start with an assignment that does not require any prerequisite (or whose prerequisites have been removed as described below).\n2. For every assignment in the chain except the last one, you must do all its $c_i$ copies (using $$c_i \times t_i$$ minutes and obtaining $$c_i \times v_i$$ importance).\n3. After fully completing an assignment, if there is any assignment $j$ with the completed assignment as a prerequisite and if the remaining time is at least $t_j$, you must choose one such assignment to continue.\n4. For the last assignment in the chain you are allowed to do a partial work (i.e. do $k$ copies with $1\le k\le c_i$) provided that you cannot or do not wish to continue with a dependent assignment.\n\nAn additional twist is that the prerequisite relations may contain cycles. In such cases, you choose not to work on any assignment that is part of a cycle.\n\nYour task is to find the maximum total importance that you can achieve within $T$ minutes following the rules above.\n\nAll formulas are in (\LaTeX) format.

inputFormat

The input begins with a line containing three integers $T$, $n$, and $M$, where $T$ is the total time available, $n$ is the number of assignments, and $M$ is the number of prerequisite relations.\n\nThen follow $n$ lines; the $i$-th of these lines contains three integers $v_i$, $t_i$, and $c_i$, representing the importance per copy, the time per copy, and the number of copies for assignment $i$, respectively.\n\nThen follow $M$ lines; each line contains two integers $a$ and $b$ indicating that assignment $a$ is a prerequisite for assignment $b$.

outputFormat

Output a single integer representing the maximum total importance you can achieve following the assignment rules within $T$ minutes.

sample

30 3 2
10 5 2
5 4 3
7 3 2
1 2
1 3

35