#1519. BUS - Đi xe buýt

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có bến xe buýt được đánh số từ đến và có tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải hoặc . Cụ thể, tuyến thứ di chuyển giữa hai bến và với giá vé do công ty quản lý quy định là . Lưu ý là giữa hai bến xe buýt có thể có nhiều hơn một tuyến xe buýt.

Hai công ty và đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều động bởi công ty mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty cũng có chính sách tương tự: khách hàng cũng chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt và nơi làm của Alice ở gần bến xe buýt nên hàng ngày Alice đều phải đi lại giữa hai bến xe này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt đến bến xe buýt .

Dữ liệu vào:

• Dòng đầu tiên chứa bốn số nguyên dương ;
• Dòng thứ trong dòng tiếp theo chứa bốn số nguyên dương mô tả tuyến xe buýt thứ , trong đó nếu tuyến này được điều hành bởi công ty hoặc nếu tuyến này được điều hành bởi công ty .

Các số trên cùng dòng được ghi cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt và thông qua tuyến xe.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt đến bến xe buýt cho Alice.

Giới hạn:

• Có số test ứng với số điểm của bài thỏa mãn điều kiện: Tất cả tuyến xe buýt được điều hành bởi công ty ;
• số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
• số test ứng với số điểm của bài thỏa mãn điều kiện: tồn tại cách đi xe buýt tối ưu trong đó Alice chỉ sử dụng tối đa một tuyến xe của công ty ;
• số test còn lại ứng với số điểm của bài không có điều kiện gì thêm.

Ví dụ:

Dữ liệu vào:

6 7 1 4
1 1 2 4
2 2 3 7
1 3 4 6
2 1 6 5
1 6 5 5
2 5 4 8
2 2 5 2

Dữ liệu ra:

12

Giải thích:

• Để đi từ đến , Alice sẽ lần lượt đi tuyến của công ty và hai tuyến của công ty . Khi đó số tiền mà Alice phải trả cho công ty là và trả cho công ty là .