Ở một ngôi làng LQDOJ nổi tiếng với truyền thống gói bánh chưng ngày Tết, shiba – một người bán bánh chưng có tiếng đang chuẩn bị mở hai gian hàng tại chợ Tết. Anh sẽ thu mua \(N\) gói bánh chưng từ \(N\) gia đình trong làng để đi bán.

Gia đình thứ \(i\) \((1 \le i \le N)\) sẽ bán đúng \(a_i\) chiếc bánh chưng trong gói của mình với giá tổng cộng là \(c_i\). shiba sẽ mua toàn bộ các gói bánh chưng này của các gia đình và phân chia chúng vào hai gian hàng.

shiba ký hiệu giá bánh chưng trung bình ở gian hàng thứ nhất là \(X_1\) và giá bánh chưng trung bình ở gian hàng thứ hai là \(X_2\). Giá bánh chưng trung bình ở một gian hàng được tính bằng tỷ lệ giữa tổng giá và tổng số lượng bánh chưng ở gian hàng đó (hay nói cách khác, \(X = \frac{Tổng \ \ giá}{Tổng \ \ số \ \ lượng \ \ bánh \ \ chưng}\)).

Để thuận lợi trong việc buôn bán ngày Tết và giữ giá cả hợp lý cho người dân, shiba muốn tích của \(X_1\) và \(X_2\) là nhỏ nhất có thể. Hay nói cách khác, anh muốn tích của giá bánh chưng trung bình ở hai gian hàng là nhỏ nhất, và shiba muốn chia làm sao mà ít nhất một gian hàng phải có đúng \(M\) gói bánh chưng, không hơn không kém.

Yêu cầu: Bạn hãy giúp shiba phân chia \(N\) gói bánh chưng vào hai gian hàng sao cho tích của \(X_1\) và \(X_2\) là nhỏ nhất có thể và có ít nhất một gian hàng phải có đúng \(M\) gói bánh chưng.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((2 \le N \le 100,1 \le M < N)\) là số gói bánh chưng và số gói bánh chưng tối thiểu phải có ở ít nhất một gian hàng.
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) \((1 \le a_i \le 100)\) là số bánh chưng có trong gói thứ \(i\), mỗi số cách nhau một khoảng trắng.
• Dòng cuối cùng chứa \(N\) số nguyên dương \(c_i\) \((1 \le c_i \le 10^6)\) là giá của gói bánh chưng thứ \(i\), mỗi số cách nhau một khoảng trắng.
• Dữ liệu vào luôn đảm bảo rằng \(a_1+a_2+...+a_N \le 500\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi làm tròn đến chữ số thập phân thứ ba.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(N \le 20\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 1
1 2 3
2 3 5

2.625