e-olymp
Competitions

Ukrainian Junior & Girls' Olympiads in Informatics, Final

Розклад

Нещодавно Козак Вус заснував власну компанію. Компанія дуже стрімко розвивається, а тому вже має багато працівників. Козак Вус поставив своїм працівникам $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}
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
3 1
1 2 3
1 2 3
Output example #1
3
Input example #2
3 100
1 2 3
3 2 1
Output example #2
10
Input example #3
3 5
1 2 3
1 2 3
Output example #3
13
Author Kostya Denisov