#1353. VACATION - Xử lý yêu cầu

Hãng hàng không Bovinia mở những chuyến bay kết nối cánh đồng, nơi những con bò sinh sống . Cũng như tất cả các hàng hàng không khác, cánh đồng trong số cánh đồng 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 Bovinia có tuyến bay một chiều , tuyến bay thứ bay từ cánh đồng đến cánh đồng và tốn USD . Có ít nhất một cánh đồng trong hai cánh đồng và là trung tâm của hãng. Ngoài ra giữa hai cánh đồng 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ó cánh đồng xuất phát và kết thúc trùng nhau.

Bessie được giao vận hành bộ phận quản lý bán vé của hãng hàng không Bovinia. Thật không may, khi cô ta mải mê gặm cỏ ngon trong vài giờ đồng hồ, đã có yêu cầu mua vé máy bay (một chiều) của những con bò , trong đó yêu cầu thứ là mua vé cho một chuyến bay từ cánh đồng đến cánh đồng .

Bessie 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 cô 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 bits.

Dữ liệu vào:

• Dòng đầu tiên ghi bốn 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