Một công ty có nhân viên đánh số từ 1 tới n. Ông chủ công ty trang bị cho mỗi nhân viên một điện thoại di động để tiện liên lạc khi làm việc. Cước phí sử dụng điện thoại sẽ do công ty chi trả.
Sau một vài tháng hoạt động, do chi phí thanh toán các hóa đơn điện thoại khá lớn nên ông chủ quyết định tìm cách giảm chi phí bằng cách yêu cầu các nhân viên của mình đăng ký sử dụng gói cước “bạn bè” của công ty viễn thông L4T (Looking for Troubles). Gói cước “bạn bè” có đặc điểm sau:
- Mỗi gói cước chỉ cho đúng hai người đăng ký tham gia, khi hai người đăng ký sử dụng gói cước “bạn bè” thì giá cước hai người đó gọi cho nhau sẽ chỉ là F (đồng/phút) thay vì R (đồng/phút) theo cước phí thông thường.
- Mỗi người chỉ được tham gia không quá một gói cước “bạn bè”
Dựa vào nhu cầu công việc, ông chủ ước lượng rằng trong mỗi tháng sẽ có m cuộc gọi đánh số từ 1 tới n, cuộc gọi thứ i do nhân viên ui gọi nhân viên vi trong ci phút. Hãy giúp ông chủ công ty yêu cầu các nhân viên của mình đăng ký sử dụng các gói cước “bạn bè” sao cho tổng số tiền điện thoại phải thanh toán hàng tháng cho các nhân viên là nhỏ nhất có thể.
Dữ liệu
- Dòng 1: Chứa hai số nguyên dương F, R (0<F<R<100)
- Dòng 2: Chứa số chẵn n (2<=n<=16)
- Dòng 3: Chứa số cuộc gọi m (1<=m<=10000)
- m dòng tiếp theo, dòng thứ i chứa ba số nguyên dương ui, vi, ci (ci<=100)
Kết quả
- Dòng 1 ghi số tiền phải trả hàng tháng theo phương án tìm được
- Các dòng tiếp, mỗi dòng ghi số hiệu hai nhân viên được yêu cầu đăng ký sử dụng gói cước “bạn bè”, các cặp số hiệu được xếp theo thứ tự từ điển