B. TRAIN

Cho thành phố và đoàn tàu, đoàn tàu thứ xuất phát tại thành phố tại thời điểm đến thành phố tại thời điểm . Để bắt được chuyến tàu thì bạn phải ở thành phố tại thời điểm , và chỉ được xuống tàu vào thời điểm tại thành phố .

Xuất phát tại thành phố vào thời điểm , bạn muốn đến thành phố . Chi phí của cả quãng đường được tính như sau:

• Bạn có thể di chuyển từ đoàn tàu sang đoàn tàu nếu và ;
• Mỗi khi chuyển từ tàu sang tàu , khoảng thời gian phải chờ tàu sẽ là , cộng thêm vào tổng chi phí ( cho trước).
• Lưu ý kể cả cũng phải tính theo công thức trên.
• Khoảng thời gian đợi giữa thời điểm và thời điểm bắt đầu tàu đầu tiên cũng coi như thời gian chờ tàu và cũng được cộng thêm vào tổng chi phí như trong công thức trên.
• Nếu bạn đến thành phố vào thời điểm thì cộng thêm vào chi phí .

Yêu cầu: tìm ra tổng chi phí nhỏ nhất có thể khi chọn các đoàn tàu tối ưu.

Dữ liệu vào:

• Dòng đầu tiên bao gồm số nguyên không âm ;
• dòng sau miêu tả các đoàn tàu, dòng thứ có số ;

Bộ test đảm bảo luôn có thể bắt tàu đi từ đến .

Dữ liệu ra:

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất có thể.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

42

Giải thích:

• Chọn tàu và tàu rồi đến thành phố tại thời điểm .

Giới hạn:

• Trong tất cả các test: ;
• Subtask số điểm có ;
• Subtask số điểm khác có ;
• Subtask số điểm khác có ;
• Subtask số điểm còn lại có .