P2648 Making Money

Adapted from another problem.

zzy now decides to travel around China and make some money along the way. In any single visit to a city, zzy can earn at most $D$ yuan. After that, he may choose to retire (i.e., stop earning) or go to other cities to work. Of course, he can work elsewhere for a while and then return to the original city to earn another $D$ yuan. The number of such round trips is unlimited. There are $P$ directed paths between cities, and there are $C$ cities in total, numbered from $1$ to $C$. Path $i$ goes from city $A_i$ to city $B_i$, and traveling along these paths costs nothing. zzy can also take a flight from one city to another. There are $F$ directed flights; the $i$-th flight goes from city $J_i$ to city $K_i$ with a cost of $T_i$ yuan. If zzy has no cash on hand, he can pay the airfare with money he will earn in the future. zzy may start earning from any city and may retire at any time and in any city. Now zzy wants to know: if there is no limit on working time, how much money can he earn in total? If the amount he can earn has no limit, output `orz`.

The first line contains $4$ space-separated positive integers $D,P,C,F$. Lines $2$ to $P+1$ each contain $2$ space-separated integers $A_i,B_i$, describing a directed path from city $A_i$ to city $B_i$. The next $F$ lines each contain $3$ space-separated positive integers $J_i,K_i,T_i$, describing a directed flight from city $J_i$ to city $K_i$ with a cost of $T_i$.

If the amount zzy can earn is unbounded, output `orz`. Otherwise, output the maximum amount of money zzy can earn under the given rules.

For $100\%$ of the testdata, $1\le D\le 1000$, $1\le P\le 200$, $2\le C\le 300$, $1\le F\le 400$, $1\le T_i \le 1000$. Translated by ChatGPT 5