프렌즈 통화 요금제

클라크(Clarke)는 작은 회사를 운영한다. 업무 특성상 모든 직원은 서로 통화할 수 있도록 휴대전화를 지급받았고, 직원들의 통화 요금은 모두 클라크가 부담한다. 그는 이 요금을 최대한 줄이고 싶다.

통신사는 '프렌즈(friends)' 서비스를 제공한다. 자주 통화하는 두 사람은 '프렌즈' 쌍을 맺을 수 있으며, 이 경우 두 사람 사이의 통화 요금이 더 저렴해진다. 단, 한 사람은 최대 하나의 프렌즈 쌍에만 속할 수 있고, 프렌즈가 아닌 다른 사람과의 통화 요금은 그대로 유지된다.

1분 통화 요금은 프렌즈 쌍이면 $F$, 그렇지 않으면 $R$이다. 즉, 두 직원 사이의 $M$분짜리 통화 하나는 두 사람이 프렌즈 쌍이면 $F \times M$, 아니면 $R \times M$의 비용이 든다. 전체 통화 요금은 모든 통화 비용의 합이다.

지난달 직원들의 통화 목록(누가 누구와 몇 분 통화했는지)이 주어질 때, 모든 직원을 $N/2$개의 프렌즈 쌍으로 짝지어 회사 전체 통화 요금을 최소로 만들고자 한다. 가능한 최소 총 통화 요금을 구하여라.

첫째 줄에 두 정수 $F$와 $R$이 공백으로 구분되어 주어진다 ($1 \le F \le R \le 100$). $F$는 프렌즈 쌍의 1분 통화 요금, $R$은 프렌즈가 아닌 경우의 1분 통화 요금이다.

둘째 줄에 직원 수를 나타내는 짝수 $N$이 주어진다 ($2 \le N \le 16$). 직원은 $1$번부터 $N$번까지 번호가 매겨져 있다.

셋째 줄에 통화 횟수 $C$가 주어진다 ($1 \le C \le 10000$).

이어지는 $C$개의 줄에는 각각 세 정수 $A$, $B$, $M$이 공백으로 구분되어 주어진다 ($1 \le A \le N$, $1 \le B \le N$, $1 \le M \le 100$). 이는 직원 $A$와 $B$가 $M$분 동안 통화했음을 뜻한다.

가능한 최소 총 통화 요금을 한 줄에 출력한다. 이는 모든 직원을 $N/2$개의 프렌즈 쌍으로 가장 알맞게 짝지었을 때 얻을 수 있는 전체 요금의 최솟값이다.