Xứ Lineland có thành phố, giữa thành phố thứ và có đường nối hai chiều. Mỗi lần vào thành phố thì phải mua vé thu phí giao thông . Tuy vậy cũng có thành phố không thu phí , thậm chí có thành phố còn tặng thêm tiền để khuyến khích mọi người tới mua bán .
Công ty giao hàng tại nhà có trụ sở đóng ở thành phố thứ và thành phố . Có một đơn giao hàng tới người ở thành phố khác nhau. Mỗi chuyến đi, xe chỉ chở được một mặt hàng cho một người. Việc giao hàng phải thực hiện theo nguyên tắc từ gần đến
xa: chỉ được đi ngang qua các thành phố đã giao hàng. Xe của công ty có một quyền ưu đãi: chỉ cần mua vé lượt đi, còn lúc về không phải mua vé (và cũng không nhận được tiền tặng). Xe ở trụ sở nào thì phải quay về trụ sở đó.
Yêu cầu: Xác định chi phí giao hàng nhỏ nhất.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên ;
Dòng thứ hai chứa số nguyên .
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là chi phí giao hàng nhỏ nhất.
