Vương quốc FYT có thành phố liên thông với nhau, được nối với nhau bằng tuyến đường hai chiều, tuyến đường hai chiều thứ có độ dài (km) nối hai thành phố và . Mỗi thành phố có duy nhất một thành viên của vương quốc FYT đang sinh sống. Để lên kế hoạch tổ chức kỳ tuyển sinh FYT, quốc vương của vương quốc FYT quyết định sẽ tổ chức một cuộc họp ở một thành phố bất kỳ trong thành phố và yêu cầu tối thiểu thành viên cùng tham gia.
Mọi thứ có vẻ như diễn ra rất thuận lợi, tuy nhiên do ảnh hưởng của dịch bệnh COVID nên mọi người không thể tự di chuyển được giữa những thành phố. Trước nguy cơ cuộc họp quan trọng sẽ bị hủy, quốc vương cấp tốc nhờ thuộc hạ của mình thuê một chiếc xe có sức chứa không giới hạn. Tuy nhiên, chiếc xe này lại rất tốn xăng. Để di chuyển quãng đường dài km, chiếc xe này cần lít xăng. Ngoài chi phí thuê xe là đồng vàng, quốc vương còn phải tốn thêm chi phí để thuê bình chứa xăng. Với mỗi lít tăng thêm của bình chứa xăng, quốc vương phải trả thêm đồng vàng. May mắn thay, ở mỗi thành phố đều có một trạm xăng. Với quyền uy của quốc vương, ngài tất nhiên sẽ được đổ xăng miễn phí.
Nhằm tiết kiệm thời gian, quốc vương quyết định di chuyển như sau: để đón thành viên, quốc vương sẽ chọn một thành phố bất kỳ và đón thành viên ở thành phố này, di chuyển qua thành phố khác, mỗi thành phố đúng một lần để đón thành viên còn lại. Ngoài tiết kiệm thời gian, quốc vương còn muốn tiết kiệm chi phí: quốc vương muốn tổng chi phí thuê xe và thuê bình chứa xăng là nhỏ nhất có thể.
Yêu cầu: Là thuộc hạ thân tín của quốc vương, bạn hãy giúp quốc vương xác định chi phí tối thiểu để thuê xe và thuê bình chứa xăng để đón được ít nhất K thành viên từ các thành phố khác nhau. Lưu ý, nếu chỉ cần tối thiểu thành viên tham gia cuộc họp thì không cần phải thuê xe.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên không âm và ;
dòng tiếp theo, dòng thứ chứa số nguyên dương và .
Dữ liệu ra:
In ra một số nguyên không âm duy nhất là chi phí tối thiểu để đón được ít nhất thành viên từ các thành phố khác nhau. Nếu không có cách di chuyển thỏa mãn, in ra .
Ví dụ:
Dữ liệu vào:
6 3
1 3 3
1 6 10
2 5 5
3 4 4
3 5 1
Dữ liệu ra:
103
Dữ liệu vào:
6 4
1 3 3
1 6 10
2 5 5
3 4 4
3 5 1
Dữ liệu ra:
105
Dữ liệu vào:
6 5
1 3 3
1 6 10
2 5 5
3 4 4
3 5 1
Dữ liệu ra:
110
Dữ liệu vào:
6 6
1 3 3
1 6 10
2 5 5
3 4 4
3 5 1
Dữ liệu ra:
-1
Giải thích:
Trong ví dụ thứ nhất, chuyến đi tối ưu bắt đầu từ thành phố thứ , di chuyển theo thứ tự , chi phí thuê xe là , chi phí thuê bình chứa xăng là (do tuyến đường dài nhất là có độ dài là ). Vì vậy, tổng chi phí là ;
Trong ví dụ thứ hai, chuyến đi tối ưu bắt đầu từ thành phố thứ , di chuyển theo thứ tự . Tổng chi phí là là (do tuyến đường dài nhất là có độ dài là );
Trong ví dụ thứ ba, chuyến đi tối ưu là . Tổng chi phí là ;
Trong ví dụ thứ tư, không tồn tại chuyến đi thỏa mãn đi qua ít nhất thành phố.
