Problem J
Quintessential Birthday Surprise

The 5 quintuplets: Ichika, Nino, Yotsuba, Itsuki and Miku are planning a birthday surprise for their tutor, Fuutarou. The sisters are smitten over Fuutarou and plan to win his heart by organising the best birthday surprise of his lifetime. Each quintuplet loves Fuutarou very much and wants him to be happy, even at the expense of themselves. Every quintuplet wants to organise multiple events and has an estimate of how much satisfaction he will receive from any particular event. More formally, each event organised by each of the quintuplets will have 3 pieces of information, namely the perceived satisfaction Fuutarou will receive from the event, $V_{i}$, the time of the event, $T_{i}$, and the organiser of the event, $E_{i}$, being one of the 5 quintuplets.

The quintuplets are trying to find a subsequence of events in chronological order from a given list to plan the birthday surprise that will result in Fuutarou’s maximum satisfaction. Since the 5 girls are not very good at mathematics, they derive a weird way of computing the satisfaction of a subsequence. The total satisfaction of the subsequence is the total sum of the product of the satisfaction of every two consecutive events. If the size of the subsequence is $1$, then the total satisfaction is just the satisfaction of that one particular event.

Furthermore, as the sisters compete for Fuutarou’s heart, conflicts begin to arise. Some of the girls do not want their events to be adjacent to some of their other sisters events in the chosen subsequence. It is also possible that there cannot exist consecutive events in the subsequence from the same quintuplet as the altruism of some of the sisters i.e. Yotsuba and Itsuki, gives them a guilty conscience and they want to give their other sisters a chance to impress Fuutarou as well!

The quintuplets have compiled a list of events that they plan to organise (not necessarily in chronological order). Can you help them find the maximum satisfaction achievable and one possible subsequence that gives this value? Every element in the subsequence corresponds to the position of the event in the list when it is rearranged in chronological order (starting from 1).

Input

The first line contains an integer $N$ ($1 \leq N \leq 200\, 000$), the number of events in the list.

There are $N$ lines that follow containing the information for each event. In particular, the $i^{th}$ line contains 3 integers, $V_{i}$ ($-10^{9} \leq V_{i} \leq 10^{9}$), $T_{i}$ ($1 \leq T_{i} \leq 10^{18}$), and $E_{i}$ ($1 \leq E_{i} \leq 5$). There are guaranteed to be at most 5 event organisers across all inputs, and each timestamp, $T_{i}$, is distinct.

The following line contains an integer $M$ ($0 \leq M \leq 15$), the number of conflicting pairs amongst the quintuplets.

There are $M$ lines that follow. The $i^{th}$ line contains 2 integers, $A_{i}$ ($1 \leq A_{i} \leq 5$) and $B_{i}$ ($1 \leq B_{i} \leq 5$), where $A_{i} \leq B_{i}$. Note that it is possible for $A_{i} = B_{i}$, where no $2$ consecutive events in the subsequence is to be organised by that same person.

Output

Output on the first line, $m$, the maximum satisfaction over all possible subsequences. The answer is guaranteed to fit inside a $64$ bit signed integer.

On the second line, output $k$, the length of the subsequence found.

On the third line, output the subsequence on one line, where every element corresponds to the position of the event in the chronologically ordered list, i.e. the $i^{th}$ event in chronological order in the list will correspond to the element denoted by $i$ in the sub-sequence (See sample input 5 for reference). If there is more than one possible subsequence, you may output any of them.

3
1 1 1
1 2 1
1 3 1
0

2
3
1 2 3 

5
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
1
1 2

3
4
1 3 4 5 

5
-1 1 1
-1 2 2
-1 3 3
-1 4 4
-1 5 5
2
1 2
4 5

2
3
1 3 4 

1
-1000000 1000000 3
0

-1000000
1
1 

3
100 2 1
200 1 2
300 3 3
2
1 2
2 3

30000
2
2 3