시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

Clarke is a successful owner of a small company. Due to the dynamics of a work, each employee got a mobile phone to talk with other employees of the same company. Clark pays all the mobile phone bills of his employees and he tries to cut them down.

He found out about a service allowing lowering phone bills under certain conditions. Two persons that often call each other can use ‘friends’ service, offered by a phone company, which makes their mutual conversation cheaper. Of course, each person can be a member of only one ‘friends’ pair and the price of talking with others stay the same.

Clever Clarke obtained a list of calls (containing who talked with whom and how long) his employees made last month. He then tried to pair his employees to make total phone bills as small as possible.

Write a program that will help Clarke to lower his company’s phone bills as much as possible using prices of ‘regular’ and ‘friends‘ phone calls and list of calls of his employees.

입력

The first line of input file contains two integers F and R, separated by a space character, 1 ≤ F ≤ R ≤ 100. Number F determines a price of one-minute conversation of  ‘friends’ pair, while number R denotes a price of one minute of ‘regular’ conversation (i.e. of people who are not in the same ‘friends’ pair).

The second line contains even integer N, 2 ≤ N ≤ 16, the number of employees.

The third line of input file contains an integer C, 1 ≤ C ≤ 10000, the number of calls.

Each of the following C lines contain three integers, separated by a space character, A, B, M, 1 ≤ A ≤ N, 1 ≤ B ≤ N, 1 ≤ M ≤ 100, meaning that employees A and B made a call with duration M minutes.

출력

The first line of output file should contain the smallest possible total payment for phone bills for given list.

The next N/2 lines should contain pairs of ‘friends’ in any order, two numbers separated with a space character.

Note: a solution needs not to be unique.

예제 입력 1

1 2
4
4
2 3 18
2 4 26
2 3 2
1 4 12

예제 출력 1

84
1 4
2 3

예제 입력 2

1 2
8
5
5 3 14
5 6 66
7 8 72
5 7 99
6 1 17

예제 출력 2

398
1 2
3 4
5 6
7 8

예제 입력 3

3 10
6
4
1 3 50
3 5 85
4 1 87
2 3 73

예제 출력 3

1746
1 4
2 6
3 5