E. Финансирование стартапа
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стартап, связанный с торговлей в интернете, просит инвесторов о финансировании. Он работает уже n недель, и у него даже есть сайт!

Для каждой недели менеджеры стартапа знают количество уникальных посетителей vi и доход ci. Чтобы оценить потенциал стартапа в промежутке с недели l по неделю r включительно, инвесторы используют минимум из максимального количества посетителей, умноженного на 100, и минимального дохода в течение этого промежутка времени. Формально:

Стоит честно заметить, что инвесторы понятия не имеют, как эффективно оценить стартап, поэтому они выберут k случайных различных недель в качестве li и дадут эти числа менеджерам стартапа. Для каждого li те выберут некоторое ri ≥ li и сообщат инвесторам максимальное количество посетителей и минимальный доход в течение соответствующего периода с li по ri.

Затем инвесторы вычислят потенциал стартапа для каждого из данных промежутков времени и выберут минимальное значение p(li, ri) в качестве итоговой оценки потенциала стартапа. Предполагается, что менеджеры стартапа всегда оптимально выбирают значения ri для данных li, то есть таким образом чтобы максимизировать итоговую оценку стартапа, чему равняется математическое ожидание этой величины?

Входные данные

В первой строке входных данных записаны два числа n и k (1 ≤ k ≤ n ≤ 1 000 000).

Во второй строке записаны n целых чисел vi (1 ≤ vi ≤ 107) — количество уникальных посетителей за каждую неделю.

В третьей строке записано n целых чисел ci (1 ≤ ci ≤ 107) — доход стартапа за каждую неделю.

Выходные данные

Выведите единственное вещественное число — математическое ожидание итоговой оценки стартапа. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.

А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если .

Примеры
Входные данные
3 2
3 2 1
300 200 300
Выходные данные
133.3333333
Примечание

Рассмотрим первый пример.

Если инвесторы спросят про li = 1, менеджеры стартапа выберут ri = 1, так чтобы максимальное число посетителей равнялось 3, а минимальный доход равнялся 300. Таким образом потенциал будет равен min(3·100, 300) = 300.

Если инвесторы спросят про li = 2, менеджеры стартапа выберут ri = 3, так чтобы максимальное число посетителей равнялось 2, а минимальный доход равнялся 200. Таким образом потенциал будет равен min(2·100, 200) = 200.

Если инвесторы спросят про li = 3, менеджеры стартапа выберут ri = 3, так чтобы максимальное число посетителей равнялось 1, а минимальный доход равнялся 300. Таким образом потенциал будет равен min(1·100, 300) = 100.

Теперь нужно выбрать равновероятно множество размера 2, в каждом выбрать минимум. Возможные множества: {200, 300},{100, 300},{100, 200}. Оценки стартапа потенциалов получаются {200, 100, 100}. Таким образом, математическое ожидание (100 + 200 + 100) / 3 = 133.(3).