Задачі
Розклад
Розклад
Нещодавно Козак Вус заснував власну компанію. Компанія дуже стрімко розвивається, а тому вже має багато працівників.
Козак Вус поставив своїм працівникам $n$ задач. $i$-та задача має два параметри: $r_i$ та $c_i$. $r_i$~--- момент часу, коли $i$-та задача повинна бути виконаною. $c_i$ --- важливість задачі (чим більше $c_i$, тим більш важлива задача).
Також Козак Вус задав деяку цілу сталу $k$.
Працівникам треба знайти такий масив $e$ з $n$ \textbf{невід'ємних} чисел, щоб наступне число було мінімально можливим:
$$\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$$
$\max(e)$ --- максимальне число масиву $e$.
Козака Вуса не цікавить сам масив $e$. Він хоче дізнатися зазначене вище мінімальне можливе значення.
Допоможіть працівникам Козака Вуса розв'язувати цю задачу.
\InputFile
Перший рядок містить два цілі числа $n$ та $k$ ($1 \le n \le 10^6, 0 \le k \le 10^9$)~--- кількість задач, які поставив Козак Вус працівникам, та стала з умови.
Другий рядок містить $n$ цілих чисел $r_1, r_2, \dots, r_n$ ($0 \le r_i \le 10^6$)~--- масив $r$.
Третій рядок містить $n$ цілих чисел $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 10^6$)~--- масив $c$.
\OutputFile
Виведіть єдине число --- мінімальне можливе значення виразу $\sum_{i=1}^{n} |r_i - e_i| \cdot c_i + \max(e) \cdot k$.
\Note
У першому прикладі масив $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$.
\Scoring
\begin{enumerate}
\item ($8$ балів): $c_i = 0$;
\item ($15$ балів): $c_i = 1$;
\item ($30$ балів): $n \le 1000$;
\item ($15$ балів): $r_i \le 100$;
\item ($32$ бали): без додаткових обмежень.
\end{enumerate}
Вхідні дані #1
3 1 1 2 3 1 2 3
Вихідні дані #1
3
Вхідні дані #2
3 100 1 2 3 3 2 1
Вихідні дані #2
10
Вхідні дані #3
3 5 1 2 3 1 2 3
Вихідні дані #3
13