F. Lễ hội trường
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lễ hội trường đã bắt đầu với những trò chơi hấp dẫn. Lễ hội có $$$n$$$ trò chơi được đánh số từ $$$1$$$ đến $$$n$$$, nếu tham gia trò chơi thứ $$$i$$$, Bảo sẽ trả $$$b_i$$$ đồng lệ phí và trò chơi có $$$p_i$$$ tỉ lệ chiến thắng. Nếu thắng, Bảo được thưởng $$$a_i$$$ đồng và nhận lại $$$b_i$$$ đồng (tổng số tiền nhận được là $$$a_i + b_i$$$ đồng).

Với mỗi trò chơi lần lượt từ $$$1$$$ đến $$$n$$$, tại trò chơi thứ $$$i$$$, Bảo có hai sự lựa chọn:

  • Tham gia trò chơi thứ $$$i$$$.
  • Bỏ qua trò chơi thứ $$$i$$$.

Vì Bảo là học sinh ưu tú, nhà trường đã cho Bảo được hưởng đặc quyền như sau. Cứ sau mỗi $$$k$$$ lần tham gia các trò chơi ($$$k$$$ là số do nhà trường chỉ định), tiền thưởng sẽ được nhân đôi ở chính xác một trò chơi sau đó.

Tức là, nếu đủ $$$k$$$ lần tham gia ở trò chơi thứ $$$i$$$, thì đặc quyền chỉ có hiệu lực ở trò chơi thứ $$$i + 1$$$, số lần tham gia trò chơi cũng sẽ được tính lại từ đầu ở lượt này. Lưu ý: Nếu bạn tham gia chơi ở lượt chơi được nhân đôi, thì lượt chơi đó vẫn sẽ được tính là một lần tham gia trò chơi.

Bảo rất háo hức trước lễ hội trường sắp tới, hãy tính giá trị kỳ vọng tối đa là số tiền mà Bảo nhận được khi lễ hội trường kết thúc.

Biết rằng tỉ lệ chiến thắng $$$p_i$$$ là độc lập cho trò chơi thứ $$$i$$$ và các sự lựa chọn có thể được quyết định bằng cách quan sát kết quả của các trò chơi trước đó.

Input

Dòng đầu tiên gồm hai số nguyên $$$n$$$ và $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le min(n, 10)$$$) — số trò chơi và số $$$k$$$ mà nhà trường chỉ định.

Dòng tiếp theo gồm $$$n$$$ số thực $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le 1$$$) — tỉ lệ thắng của các trò chơi.

Dòng tiếp theo gồm $$$n$$$ số nguyên $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$) — số tiền nhận được khi chiến thắng.

Dòng tiếp theo gồm $$$n$$$ số nguyên $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^4$$$) — lệ phí tham gia trò chơi.

Output

In ra một số thực duy nhất là giá trị kỳ vọng tối đa khi lễ hội trường kết thúc, đáp án của bạn được cho là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án của ban tổ chức không quá $$$10^{-6}$$$.

Examples
Input
2 2
0.3 0.6
10 3
2 5
Output
1.6
Input
3 2
0.3 0.6 0.5
10 3 2
2 5 1
Output
2.9
Input
5 2
0.5 0.2 0.7 0.9 0.1
3 3 2 8 2
3 2 10 4 5
Output
12.4
Note

Ở ví dụ thứ nhất, Bảo tham gia trò chơi đầu tiên và bỏ qua trò chơi thứ hai.

Ở ví dụ thứ hai, Bảo tham gia tất cả trò chơi.

Ở ví dụ thứ ba, tham gia trò chơi thứ nhất, thứ ba và thứ tư.