Уже не первый год в Байтландии идёт тяжелая борьба за быструю отрисовку страниц в интернете...

Одним из шагов к победе стало нововведение Баннерной крутилки: отдавать баннеры для нескольких блоков в одном ответе, тем самым сохранив дополнительные вызовы, а с ними и время. Однако оказалось, что совсем непросто разумно разбить полученные баннеры по блокам.

Имеется $$$N$$$ баннеров, которые мы хотим разбить на $$$K$$$ блоков. В ответе есть массив $$$P$$$, где $$$P_i$$$ — прогнозируемая польза от показа $$$i$$$-го баннера, а также массив $$$L$$$, где $$$L_{j}$$$ — возможная потеря внимания пользователя на $$$j$$$-й по счёту блок.

Аналитик Виталик тестирует гипотезы, которые должны в первую очередь повысить счастье пользователя. Сейчас он прорабатывает следующую метрику: для блока вводим функцию $$$f(Block_{s}) = P_{min} \cdot len(Block_{s}) - L_{s} P_{max}$$$, где $$$P_{min}$$$ — минимальное значение $$$P$$$ среди баннеров в блоке, $$$P_{max}$$$ — максимальное, $$$len(Block_{s})$$$ — количество баннеров в блоке, $$$s$$$ — номер блока в разбиении. Значением метрики для конкретного разбиения является сумма значений $$$f$$$ для всех блоков в этом разбиении. На каждом запросе необходимо находить разбиение, которое максимизирует эту метрику.

Виталик умеет решать эту задачу, но его алгоритм оказался не очень быстрым. Вас, как эксперта, попросили помочь ему и ускорить отбор!