Розклад#10469

Розклад

2 секунди

256 мегабайтів

Легка

Нещодавно Козак Вус заснував власну компанію. Компанія дуже стрімко розвивається, а тому вже має багато працівників.

Козак Вус поставив своїм працівникам $n$ задач. $i$ -та задача має два параметри: $r_{i}$ r_i та $c_{i}$ c_i. $r_{i}$ r_i — момент часу, коли $i$ -та задача повинна бути виконаною. $c_{i}$ c_i — важливість задачі (чим більше $c_{i}$ c_i, тим більш важлива задача).

Також Козак Вус задав деяку цілу сталу $k$ .

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

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

\sum_{i=1}^{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

= |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}$ 1 \le n \le 10^6, 0 \le k \le 10^9) — кількість задач, які поставив Козак Вус працівникам, та стала з умови.

Другий рядок містить $n$ цілих чисел $r_{1}, r_{2}, \dots, r_{n}$ r_1, r_2, \dots, r_n ( $0 \leq r_{i} \leq 1 0^{6}$ 0 \le r_i \le 10^6) — масив $r$ .

Третій рядок містить $n$ цілих чисел $c_{1}, c_{2}, \dots, c_{n}$ c_1, c_2, \dots, c_n ( $0 \leq c_{i} \leq 1 0^{6}$ 0 \le c_i \le 10^6) — масив $c$ .

Вихідні дані

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

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

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

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

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

Оцінювання

( $8$ балів): $c_{i} = 0$ c_i = 0;
( $15$ балів): $c_{i} = 1$ c_i = 1;
( $30$ балів): $n \leq 1000$ n \le 1000;
( $15$ балів): $r_{i} \leq 100$ r_i \le 100;
( $32$ бали): без додаткових обмежень.