20720번 - Premier League 다국어

Andrew and Jordan are massive Pokemon fans, and have many friends who are also huge fans of Pokemon as well. However, both of them are very competitive! To satisfy their competitive nature, you are going to host a mini premier draft tournament, the Premier League! Both Andy and Jordan have submitted bids to rent out each Pokemon from your inventory, and then will begin use their rented Pokemon in a series of battles! To ensure that the battles are fair, you set up a schedule of battles before the fans submitted their bids. Note that if a battle is between two Pokemon owned by the same trainer, the battle will not occur because the trainer will win either way.

As the tournament organizer, you don't really care who wins. However, you do care about the cost to host this tournament. While you fortunately have access to a gym where the battles can take place, you also know that the gym charges a battle fee to cover preparation and post-battle healing. Furthermore, acquiring each Pokemon costs a good amount of money! Even though Andy and Jordan each want as many Pokemon as possible, both may be willing to pay different prices for each individual Pokemon.

Now that the bids are in, you have to decide which fan wins the bid for each Pokemon. Given the battle schedule, the cost of each Pokemon for you, how much Andy and Jordan are willing to pay for each Pokemon, as well as the costs of the battles, determine the cheapest total cost for you to organize this extravagant showdown! Bear in mind all Pokemon need to be assigned to either Andy or Jordan.

The first line of input contains $1 \le n \le 10^2$, the number of Pokemon that are available for purchase. The following $n$ lines each contain $3$ integers $1 \le c_i, a_i, j_i \le 10^5$, where $a_i, j_i \le c_i$, which are the cost for you to acquire the $i^{th}$ Pokemon, Andy's bid for the $i^{th}$ Pokemon, and Jordan's bid for the $i^{th}$ Pokemon, respectively.

The next line contains $1 \le b \le 5 \cdot 10^2$, the number of battles to occur. After that, the next $b$ lines each contain three integers $1 \le a_j, b_j \le n, 1 \le c_j \le 10^5$, signifying that the $j^{th}$ battle will occur between Pokemon $a_j$ and $b_j$ and will cost $c_j$ if it occurs. Note that there may be multiple battles between the same pairs of Pokemon.

Output a single number, the minimum total cost to run this tournament. Note that while many Pokemon may be expensive, you can offset the costs with Andy and Jordan's bids.