Friends Calling Plan

Clarke runs a small company. Because of the nature of the work, every employee was given a mobile phone so they can talk with other employees, and Clarke pays all of their phone bills. He wants to cut those bills as much as possible.

The phone company offers a 'friends' service: two people who often call each other may form a 'friends' pair, which makes the calls between the two of them cheaper. Each person may belong to at most one friends pair, and the price of talking with anyone else stays the same.

The price of a one-minute call is $F$ for a friends pair and $R$ otherwise. In other words, a single $M$-minute call between two employees costs $F \times M$ if the two are a friends pair, and $R \times M$ otherwise. The total bill is the sum of the cost of every call.

Given last month's list of calls (who talked with whom and for how long), pair all employees into $N/2$ friends pairs so that the company's total phone bill is as small as possible. Compute the smallest possible total bill.

The first line contains two integers $F$ and $R$ separated by a space ($1 \le F \le R \le 100$). $F$ is the price of a one-minute call for a friends pair, and $R$ is the price of a one-minute call for people who are not a friends pair.

The second line contains an even integer $N$ ($2 \le N \le 16$), the number of employees, numbered from $1$ to $N$.

The third line contains an integer $C$ ($1 \le C \le 10000$), the number of calls.

Each of the next $C$ lines contains three integers $A$, $B$, and $M$ separated by spaces ($1 \le A \le N$, $1 \le B \le N$, $1 \le M \le 100$), meaning that employees $A$ and $B$ had a call lasting $M$ minutes.

Print, on a single line, the smallest possible total phone bill, i.e. the minimum total cost achievable by pairing all employees into $N/2$ friends pairs in the best possible way.