Cửa hàng bán hoa

Xem PDF

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

SK mở hai cửa hàng bán hoa và nhập hoa từ \(N\) vườn. Mỗi vườn có \(A_i\) bông hoa với tổng giá trị là \(C_i\). SK sẽ mua hết số hoa trong \(N\) vườn và đưa đến hai cửa hàng của mình. Hoa của một vườn chỉ có thể đưa đến một cửa hàng duy nhất.

Với giá hoa trung bình tại cửa hàng 1 là \(P_1\), giá hoa trung bình tại cửa hàng hai là \(P_2\) và giá hoa trung bình trong mỗi cửa hàng được tính bằng tổng giá trị hoa chia cho số bông hoa có trong cửa hàng đó, SK muốn phân chia hoa về các cửa hàng sao cho tích \(P_1 \times P_2\) là nhỏ nhất có thể.

Yêu cầu: Giúp SK phân chia hoa về hai cửa hàng sao cho \(P_1 \times P_2\) là nhỏ nhất có thể, với chú ý sau khi phân chia hoa về các cửa hàng thì phải có ít nhất một cửa hàng nhận hoa từ \(L\) vườn.

Input

  • Dòng 1 gồm hai số nguyên \(N\)\(L\) (\(2 \le N \le 100,1 \le L < N\)) – số bông hoa và số hoa trong ít nhất một cửa hàng.
  • Dòng 2 gồm \(N\) số nguyên \(A_i (1 \le A_i \le 100)\), tổng các số nguyên \(A_i \le 500\).
  • Dòng 3 gồm \(N\) số nguyên \(C_i (1 \le C_i \le 1000000)\).

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output

  • Ghi ra một số thực duy nhất là tích \(P_1 \times P_2\) nhỏ nhất có thể (làm tròn tới ba chữ số phần thập phân).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N\le 20\).
  • Subtask \(2\) (\(70\%\) số điểm): Không có điều kiện gì thêm.

Example

Test 1

Input
3 1
3 2 1
1 2 3
Output
0.556

Test 2

Input
3 2
2 2 2
3 3 3
Output
2.250

Bình luận

Không có bình luận nào.