Bài 3 (5đ): Tham quan

Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức học thi Tin trẻ tổ chức cho~ N~ đoàn (đánh từ số 1 đến N) mỗi đoàn đi tham quan một địa điểm khác nhau. Đoàn thứ i đi tham địa điểm ở cách Khách sạn Hoàng Đế đi dᵢ km (i = 1, 2, …, N).

Hội thi có M xe taxi đánh số từ 1 đến ~M (N ≤ M)~ để phục vụ đưa các đoàn đi tham quan. Xe thứ j có mức tiêu thụ xăng là vⱼ lít/km.

Yêu cầu:

Hãy chọn N xe để phục vụ việc đưa các đoàn đi tham quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.

Dữ liệu vào :

Dòng đầu tiên chứa hai số nguyên dương ~N, M~ (~N ≤ M ≤ 200~). Dòng thứ hai chứa các số nguyên dương ~d₁, d₂, …, dₙ~.

Dòng thứ ba chứa các số nguyên dương ~v₁, v₂, …, vₘ~.

Kết quả gồm:

Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi tham quan (không tính lượt về).

Dòng thứ i trong ~N~ dòng tiếp theo ghi chỉ số xe phục vụ đoàn ~i~ (~i = 1, 2, …, N~).

Input:

3 4
7 5 9
17 13 15 10

Output:

256
2
3
4