Hide

Problem H
Hungarian Services

You have been hired by Hungarian Services to match a list of $m$ problem proposals to a list of $n$ problem topics for a contest, where $m \geq n$. The problem proposals have an index of $1, 2, \ldots , m$, while the topics have an index of $1, 2, \ldots n$.

Not all problems are suitable for all topics. You will be given $r$ tuples of $(a_ i, b_ i, c_ i)$ denoting that problem proposal $b_ i$ can be matched to topic $a_ i$ with suitability of $c_ i$. In a valid matching, each topic must be matched to exactly one suitable problem, while each problem can be matched to at most one topic.

Alas! it is not always possible to have a valid matching. A partial matching is a valid matching where some of the $n$ topics may be unmatched. Your task is to find the minimum number of unmatched topics among all partial matchings. Among partial matchings that minimize the number of unmatched topics, maximize the sum of suitability of problem proposals to topics within the partial matching.

Input

The first line contains three integers $n$, $m$ and $r$, $(1\leq m \leq n \leq 400; 1 \leq r \leq nm)$ — the number of topics, the number of problem proposals and the number of suitable pairs of problem proposals and topics.

The $i^{th}$ of the following $r$ lines contains three integers $a_ i, b_ i, c_ i$, $(1 \leq a_ i \leq n, 1 \leq b_ i \leq m, 1 \leq c_ i \leq 10)$, where problem $b_ i$ can be matched to topic $a_ i$ with suitability $c_ i$. It is guaranteed that all $(a_ i, b_ i)$ pairs are unique.

Output

Output two integers — the minimum number of unmatched topics, and the maximum sum of suitability of problem proposals to topics within the partial matching.

Sample Input 1 Sample Output 1
2 2 4
1 1 1
2 2 1
1 2 2
2 1 2
0 4
Sample Input 2 Sample Output 2
3 4 5
1 2 1
1 3 1
1 4 1
2 4 2
3 4 3
1 4
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Zhang Guangxuan
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in