Problem Description

In a certain class, there are $ N $ girls and $ M $ boys. The girls are assigned attendance numbers from $ 1 $ to $ N $, and the boys are assigned attendance numbers from $ 1 $ to $ M $.

The Cupid of Luck will form a travel group consisting of $ P $ girls and $ Q $ boys from these students.

The $ N $ girls together have $ R $ chocolates, numbered from $ 1 $ to $ R $.

Chocolate $i\ (1\ ≦\ i\ ≦\ R)$ is held by the girl with attendance number $ x_i $, and is intended to be given to the boy with attendance number $ y_i $ during the trip. The chocolate can only be successfully given if both the girl with attendance number $ x_i $ and the boy with attendance number $ y_i $ are included in the travel group. If the chocolate $ i $ is successfully given, the happiness value is $ z_i $.

What is the maximum possible total happiness value from the successfully given chocolates?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ P $ $ Q $ $ R $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ : $ x_R $ $ y_R $ $ z_R $

• The first line contains five integers $N\ (1\ ≦\ N\ ≦\ 18)$, $M\ (1\ ≦\ M\ ≦\ 18)$, $P\ (1\ ≦\ P\ ≦\ N)$, $Q\ (1\ ≦\ Q\ ≦\ M)$, $R\ (1\ ≦\ R\ ≦\ N×M)$, separated by spaces. This indicates that there are $ N $ girls, $ M $ boys, the travel group consists of $ P $ girls and $ Q $ boys, and there are $ R $ chocolates.
• The next $ R $ lines provide information about the chocolates. The $i\ (1\ ≦\ i\ ≦\ R)$ line contains three integers $x_i\ (1\ ≦\ x_i\ ≦\ N)$, $y_i\ (1\ ≦\ y_i\ ≦\ M)$, $z_i\ (1\ ≦\ z_i\ ≦\ 10,000)$, separated by spaces. This indicates that chocolate $ i $ is held by the girl with attendance number $ x_i $, intended to be given to the boy with attendance number $ y_i $, and has a happiness value of $ z_i $.
• For integers $ i $ and $ j $ where $1\ ≦\ i\ ＜\ j\ ≦\ R$, it holds that $ x_i≠x_j $ or $ y_i≠y_j $.

Output Format

Output the maximum possible total happiness value from the successfully given chocolates in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 4 2 3 7
1 1 9
1 2 7
1 3 15
1 4 6
2 2 3
2 4 6
3 3 6

Sample Output #1

37

Sample Input #2

4 5 3 2 9
2 3 5
3 1 4
2 2 2
4 1 9
3 5 3
3 3 8
1 4 5
1 5 7
2 4 8

Sample Output #2

26

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve the dataset $ 1 $ where $N\ ≦\ 8$ and $M\ ≦\ 8$, you will be awarded $ 30 $ points.

Sample Explanation 1

Consider a travel group consisting of the girls with attendance numbers $ 1 $, $ 2 $ and the boys with attendance numbers $ 2 $, $ 3 $, $ 4 $.

• Chocolate $ 1 $ will not be given because the boy with attendance number $ 1 $ does not participate in the trip.
• Chocolate $ 2 $ will be successfully given because both the girl and the boy are participating in the trip. The happiness value is $ 7 $.
• Chocolate $ 3 $ will be successfully given because both the girl and the boy are participating in the trip. The happiness value is $ 15 $.
• Chocolate $ 4 $ will be successfully given because both the girl and the boy are participating in the trip. The happiness value is $ 6 $.
• Chocolate $ 5 $ will be successfully given because both the girl and the boy are participating in the trip. The happiness value is $ 3 $.
• Chocolate $ 6 $ will be successfully given because both the girl and the boy are participating in the trip. The happiness value is $ 6 $.
• Chocolate $ 7 $ will not be given because the girl with attendance number $ 3 $ does not participate in the trip.

The total happiness value is $7\ +\ 15\ +\ 6\ +\ 3\ +\ 6\ =\ 37$, which is the maximum value.

见题面 Input 部分

见题面 Output 部分