Расписание

Простая

Ограничение по времени выполнения 2 секунды

Ограничение по использованию памяти 256 мегабайт

Казак Вус недавно основал свою компанию, которая быстро растет и уже насчитывает множество сотрудников.

Он поручил своим сотрудникам $n$ задач. Каждая $i$ -я задача характеризуется двумя параметрами: $r_{i}$ и $c_{i}$ . Здесь $r_{i}$ — это момент времени, к которому задача должна быть выполнена, а $c_{i}$ — важность задачи (чем больше $c_{i}$ , тем важнее задача).

Кроме того, Казак Вус задал некоторое целое постоянное $k$ .

Сотрудникам необходимо определить такой массив $e$ из $n$ неотрицательных чисел, чтобы минимизировать следующее выражение:

i = 1 \sum n ∣ r_{i} - e_{i} ∣ \cdot c_{i} + max (e) \cdot k =

= ∣ r_{1} - e_{1} ∣ \cdot c_{1} + ∣ r_{2} - e_{2} ∣ \cdot c_{2} + \dots + ∣ r_{n} - e_{n} ∣ \cdot c_{n} + max (e) \cdot k

Здесь $max (e)$ — это максимальное значение в массиве $e$ .

Казак Вус не интересуется самим массивом $e$ . Он хочет узнать минимально возможное значение указанного выражения.

Помогите сотрудникам Казака Вуса решить эту задачу.

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

Первая строка содержит два целых числа $n$ и $k$ ( $1 \leq n \leq 1 0^{6}, 0 \leq k \leq 1 0^{9}$ ) — количество задач, поставленных Казаком Вусом, и постоянная из условия.

Вторая строка содержит $n$ целых чисел $r_{1}, r_{2}, \dots, r_{n}$ ( $0 \leq r_{i} \leq 1 0^{6}$ ) — массив $r$ .

Третья строка содержит $n$ целых чисел $c_{1}, c_{2}, \dots, c_{n}$ ( $0 \leq c_{i} \leq 1 0^{6}$ ) — массив $c$ .

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

Выведите единственное число — минимально возможное значение выражения $\sum_{i = 1}^{n} ∣ r_{i} - e_{i} ∣ \cdot c_{i} + max (e) \cdot k$ .

Примеры

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Ввод #3

Ответ #3

Примечание

В первом примере массив $e$ , при котором достигается минимальное значение, выглядит так: $[1, 2, 3]$ . Тогда минимальное значение равно $∣1 - 1∣ \cdot 1 + ∣2 - 2∣ \cdot 2 + ∣3 - 3∣ \cdot 3 + 3 \cdot 1 = 3$ .

Во втором примере массив $e$ , при котором достигается минимальное значение, выглядит так: $[0, 0, 0]$ . Тогда минимальное значение равно $∣1 - 0∣ \cdot 3 + ∣2 - 0∣ \cdot 2 + ∣3 - 0∣ \cdot 1 + 0 \cdot 100 = 10$ .

В третьем примере массив $e$ , при котором достигается минимальное значение, выглядит так: $[1, 2, 2]$ . Тогда минимальное значение равно $∣1 - 1∣ \cdot 1 + ∣2 - 2∣ \cdot 2 + ∣3 - 2∣ \cdot 3 + 2 \cdot 5 = 13$ .

Оценивание

( $8$ баллов): $c_{i} = 0$ ;
( $15$ баллов): $c_{i} = 1$ ;
( $30$ баллов): $n \leq 1000$ ;
( $15$ баллов): $r_{i} \leq 100$ ;
( $32$ балла): без дополнительных ограничений.

Отправки 417

Коэффициент принятия 26 %