Two potato stores

Split N potato bags into two stores with one store holding exactly L bags to minimize the product of the two average potato prices.

Medium6Dynamic programmingNo attempts yetTime limit1sMemory limit64 MB

Problem

A shopkeeper is opening two stores that sell potatoes. He buys potatoes from NN farmers. Farmer ii sells one bag holding aia_i potatoes for a total price of cic_i. The shopkeeper buys every bag and puts each bag, whole, into one of the two stores.

Write P1P_1 for the average potato price in the first store and P2P_2 for the average potato price in the second store. The average potato price in a store is the sum of the bag prices in that store divided by the number of potatoes in that store. Because of shipping and stock limits, the shopkeeper wants the product of P1P_1 and P2P_2 to be as small as possible.

In the chosen division, at least one of the two stores must hold exactly LL bags.

Input

The first line contains two integers NN and LL (2N1002 \le N \le 100, 1L<N1 \le L < N), the number of bags and the number of bags that at least one store must hold.

The second line contains NN integers aia_i (1ai1001 \le a_i \le 100), separated by spaces.

The third line contains NN integers cic_i (1ci10000001 \le c_i \le 1\,000\,000), separated by spaces.

The sum of all aia_i is at most 500.

Output

Print, on a single line, the smallest possible product of P1P_1 and P2P_2 with exactly three digits after the decimal point. Round the fourth decimal digit half up and pad with zeros so that three digits always appear.