On the occasion of its $10$year anniversary, an ecommerce
company is running a campaign to engage with their loyal
customers. They have prepared $m$ gifts, numbered from $1$ to $m$, to thank its loyal customers
where each customer will receive no more than one gift. The
company has $n$ loyal
customers, numbered from $1$ to $n$. In order to ensure that customers
are satisfied with the gift they receive, the company decided
to conduct a customer survey. The customer survey result is
recorded by the feedback cards, each of which can be described
by a tuple of three positive integers $(i,j,p)$ indicating that customer
$i$ has a satisfaction
level of $p$ if he or she
receives the gift $j$.
Each customer will give his or her level of satisfaction for
every gift unless he/she has a satisfaction level of
$0$. At the end, the
company receives $k$
feedback cards from their loyal customers.
Based on the result of the customer survey, your task is to
determine how to send gifts to loyal customers to bring the
greatest sum of satisfaction of all customers receiving the
gifts.
Input

The first line contains three integers $m$, $n$, $k$ $(1 \leq m,n \leq 1\, 000, \; 1 \leq k
\leq m \times n)$;

The next $k$ lines
describe the customer survey results, each of which
contains three positive integers $i, j, p$ described above
$(1 \leq i \leq n, \; 1 \leq
j \leq m, \; 1 \leq p \leq 30\, 000)$. It is
guaranteed that no $2$
surveys have same $i$
and $j$.
Output

The first line contains an integer that is the greatest
sum of satisfaction of all customers;

The second line contains the integer $s$ – the number of gifts that
must be sent to the customers;

The next $s$ lines
describe how the gifts are sent: each line contains two
integers $x,y$
indicating that the customer $x$ receives the gift $y$.
If there are more than one solutions giving the greatest sum
of satisfaction, you can print any of them.
Sample Input 1 
Sample Output 1 
3 2 4
1 1 2
1 2 3
1 3 5
2 3 8

11
2
1 2
2 3
