Mô tả và yêu cầu

Công ty khai thác khoáng sản có 𝑛 mỏ khai thác, mỏ khoáng sản thứ 𝑖 nằm ở tọa
độ 𝑥𝑖 và mỗi ngày khai thác được 𝑐𝑖 tấn khoáng sản thô. Để giảm thiểu chi phí vận
chuyển công ty quyết định xây dựng 𝑘 nhà máy chế biến. Vào cuối ngày, tất cả khoáng
sản thô từ các mỏ khai thác đều được vận chuyển về 𝑘 nhà máy này để chế biến.

Yêu cầu: Hãy giúp công ty chọn 𝑘 địa điểm để xây dựng nhà máy chế biến sao cho tổng
chi phí vận chuyển là thấp nhất. Biết rằng chi phí vận chuyển 𝟏 tấn khoáng sản thô từ
một mỏ khoáng sản đến nhà máy chế biến gần nhất là khoảng cách giữa mỏ khoáng sản
đến nhà máy chế biến đó. Lưu ý rằng địa điểm xây dựng nhà máy chế biến có thể nằm
tại mỏ khoáng sản.

Dữ liệu: Vào từ file văn bản KTKS.INP gồm:

 Dòng 1: Chứa hai số nguyên dương 𝑛, 𝑘 (1 ≤ 𝑛 ≤ 1000, 1 ≤ 𝑘 ≤ 30, 𝑘 ≤ 𝑛).
 Dòng 2: Chứa 𝑛 số nguyên 𝑥1, 𝑥2, … ,𝑥𝑛 (0 ≤ 𝑥𝑖 ≤ 109).
 Dòng 3: Chứa n số nguyên 𝑐1, 𝑐2, … ,𝑐𝑛 (0 ≤ 𝑐𝑖 ≤ 105).

Kết quả: Ghi ra file văn bản KTKS.OUT gồm:

 Ghi ra một số nguyên duy nhất là tổng chi phí vẫn chuyển khoáng sản từ tất cả
các mỏ đến các nhà máy chế biến.

Ví dụ

KTKS.INP                                          KTKS.OUT
 4 2                                               3
 1 2 3 5
 1 2 2 3
Ràng buộc:
       Có  40%  số    test  của  bài  có   1  ≤   𝑘  ≤   𝑛  ≤   20, 0  ≤   𝑥𝑖  ≤  103,  1  ≤   𝑐𝑖 ≤
         103.

       Có 20% số test của bài có 1      ≤  𝑛  ≤  100,  1 ≤  𝑘  ≤  30, 𝑘  ≤  𝑛,0  ≤  𝑥𝑖 ≤  106,  1 ≤
        𝑐𝑖 ≤  103.

       Có 40% số test của bài không giới hạn gì thêm.