Đường sắt đô thị


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Vùng đô thị Vinh mở rộng nổi tiếng với hệ thống đường sắt đô thị lớn bậc nhất thế giới. Với quy mô hàng trăm đoàn tàu điện cũng như hàng nghìn km đường ray nổi, ngầm hay trên cao, hệ thống Vinh Metro giúp người dân và khách du lịch di chuyển đến toàn bộ khu vực nội thành, ngoại thành và ven đô một cách dễ dàng.

Hiện tại, có một tuyến cần được nâng cấp. Tuyến Kỳ Sơn xuất phát từ ga Bến Thủy đến ga Nậm Cắn có độ dài $l$ km. Người dân khi đi trên tuyến này cần đổi tàu $n$ lần (tính cả lần lên tàu tại ga Bến Thủy).

Xem ga Bến Thủy là ga thứ nhất đặt tại km số $0$, ga Nậm Cắn là ga thứ $n+1$ đặt tại km số $l$. Các ga trên đường đi - nơi người dân cần đổi tàu lần lượt được đặt tại km số $a_2,a_3,a_4,...,a_n$. Đoàn tàu khởi hành từ ga thứ $i$ chạy với vận tốc $b_i$ phút$/km$.

Nhận thấy một số đoàn tàu trên tuyến Kỳ Sơn đã cũ, công ty Vinh Metro dự định dừng sử dụng tối đa $k$ đoàn tàu. Nếu ngưng sử dụng đoàn tàu xuất phát từ ga thứ $i$, người dân sẽ không cần đổi tàu tại ga này, mà tiếp tục ngồi trên tàu trước đó, di chuyển đến ga gần nhất vẫn đang sử dụng và đổi tàu tại đây. Do luôn cần tàu từ ga Bến Thủy, nên công ty sẽ không loại đoàn tàu từ ga này.

Hãy giúp Vinh Metro loại tối đa $k$ đoàn tàu khỏi đội tàu để thời gian di chuyển từ ga Bến Thủy đến ga Nậm Cắn là ngắn nhất.

Dữ liệu

  • Dòng đầu tiên chứa ba số nguyên $n,l,k (1\le n \le 500;1\le l \le 10^5;0 \le k \le n);$
  • Dòng tiếp theo chứa $n$ số nguyên $a_i (a_1=0; a_i < a_{i+1};0<a_i < l);$
  • Dòng cuối cùng chứa $n$ số nguyên $b_i (1 \le b_i \le 10^5).$

Kết quả

  • Thời gian di chuyển ngắn nhất có thể từ ga Bến Thủy đến ga Nậm Cắn.

Chấm điểm

30; $n \le 20$. 20; $k \le 2$. 50; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

4 13 0
0 4 6 9
3 6 2 7

output

58
Ví dụ 2

input

4 13 1
0 4 6 9
3 6 2 7

output

38

Giải thích

Với ví dụ 1, không loại đoàn tàu nào. Người dân sẽ khởi hành từ ga Bến Thủy (km 0), di chuyển đến ga Hưng Đạo (km 4) trong $4 \times 3 = 12$ phút. Khởi hành từ ga Hưng Đạo đến ga Kim Liên (km 6) trong $2 \times 6 = 12$ phút. Từ ga Kim Liên đến ga Hòa Bình (km 9) trong $3 \times 2 = 6$ phút. Và từ ga Hòa Bình đến ga Nậm Cặn trong $4 \times 7 = 28$ phút. Tổng thời gian di chuyển là $58$ phút.

Với ví dụ 2, loại đoàn tàu thứ 4. Như vậy người dân sau khi khởi hành từ ga Kim Liên sẽ trực tiếp đến ga Nậm Cắn trong thời gian $7 \times 2 =14$ phút. Tổng thời gian di chuyển là $38$ phút.


Comments

There are no comments at the moment.