• Tên file bài làm: NETWORK1.cpp
• File dữ liệu vào: NETWORK1.INP
• File kết quả: NETWORK1.OUT
• Thời gian chạy: 1.0 giây

Đề bài

Hệ thống gồm ~n~ máy tính, máy thứ ~i~ có ~c_i~ cổng kết nối. Các máy được chia vào ~k~ trạm, trạm thứ ~j~ có ~x_j~ máy tính. Có ~m~ yêu cầu liên lạc dạng ~(u, v)~: Mỗi máy trong trạm ~u~ muốn liên lạc với từng máy trong trạm ~v~.

Cần thiết lập mạng hai chiều sao cho:

1. Mọi yêu cầu liên lạc đều được đáp ứng (trực tiếp hoặc gián tiếp).
2. Số kết nối của mỗi máy ~i~ không vượt quá ~c_i~.
3. Định nghĩa độ trễ mạng như sau: xét cặp máy ~(x, y)~ (~x \neq y~) bất kì, mà ~x~ cần truyền tin cho ~y~. Đặt ~d(x,y)~ là đường truyền ngắn nhất (đi qua ít kết nối nhất) giữa hai máy này. Độ trễ của hệ thống sẽ là ~\max(d(x,y))~ với mọi cặp ~x,y~ tùy ý. Gọi độ trễ này là ~L~.
4. Hàm mục tiêu ~f = E \times n + L~ đạt giá trị nhỏ nhất, trong đó ~E~ là tổng số kết nối, ~L~ là độ trễ lớn nhất giữa các cặp máy cần truyền tin.

Hãy thiết kế một hệ thống mạng có ~f~ nhỏ nhất.

Lưu ý: Vì quy mô hệ thống rất nhỏ (~n \le 6~), hãy dùng phương pháp duyệt toàn bộ cấu hình để tìm mạng tối ưu.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên ~n, k, m~ (~1 \le k \le n \le 6, 1 \le m \le 36~).
• Dòng tiếp theo chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ (~1 \le c_i \le n~).
• Tiếp theo là ~k~ nhóm dòng mô tả ~k~ trạm: dòng 1 ghi ~x_j~, dòng 2 ghi ~x_j~ số hiệu máy tính.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số ~u, v~ (~1 \le u, v \le k~) là yêu cầu giữa trạm ~u~ và ~v~.

Kết quả

• Dòng đầu ghi số nguyên ~f~ nhỏ nhất.
• ~E~ dòng tiếp theo ghi các cạnh kết nối ~u \ v~ (~u < v~).

Ví dụ