#1109. ABCAIR - Xử lý yêu cầu

Hãng hàng không mở những chuyến bay kết nối thành phố . Cũng như tất cả các hãng hàng không khác, thành phố trong số thành phố trên được thiết kế như là trung tâm của hãng .

Hiện tại, hãng hàng không có tuyến bay một chiều , tuyến bay thứ bay từ thành phố đến thành phố và tốn USD . Có ít nhất một thành phố trong hai thành phố và là trung tâm của hãng. Ngoài ra giữa hai thành phố có không quá một tuyến bay trực tiếp (theo cả hai hướng) và không có tuyến bay nào có Thành phố xuất phát và kết thúc trùng nhau.

BT được giao vận hành bộ phận quản lý bán vé của hãng hàng không . Thật không may, khi anh ta mải mê chơi điện tử trong vài giờ đồng hồ, đã có yêu cầu mua vé máy bay (một chiều) của hành khách , trong đó yêu cầu thứ là mua vé cho một chuyến bay từ thành phố đến thành phố .

BT choáng ngợp vì khối lượng công việc đồ sộ đến như vậy. Bạn hãy viết chương trình giúp anh ta tính xem mỗi yêu cầu như vậy có thể thực hiện được không và nếu thực hiện được thì giá tiền nhỏ nhất phải trả là bao nhiêu?

Để giảm thiểu kích thước của dữ liệu ra, bạn chỉ cần in ra tổng số yêu cầu có thể thực hiện được và tổng số giá tiền nhỏ nhất cho chúng. Để ý rằng con số này có thể vượt qua kiểu số nguyên bit.

Dữ liệu vào:

• Dòng đầu tiên ghi số tự nhiên và
• dòng tiếp theo, dòng thứ ghi ba số
• dòng tiếp theo, mỗi dòng ghi mã của một trung tâm (trong giới hạn )
• dòng cuối cùng, dòng thứ ghi yêu cầu bay thứ là hai số nguyên

Dữ liệu ra:

• Dòng đầu ghi tổng số lượng yêu cầu bay có thể đáp ứng được
• Dòng sau ghi tổng giá tiền nhỏ nhất của các yêu cầu bay đáp ứng được

Ví dụ:

Dữ liệu vào:

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

Dữ liệu ra:

1
20