Розклад

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

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

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

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

$\max (e)$ — максимальне число масиву $e$.

Козака Вуса не цікавить сам масив $e$. Він хоче дізнатися зазначене вище мінімальне можливе значення.

Допоможіть працівникам Козака Вуса розв'язувати цю задачу.

Input

Перший рядок містить два цілі числа $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$.

Output

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

Examples

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

1. ($8$ балів): $c_i=0$;

2. ($15$ балів): $c_i=1$;

3. ($30$ балів): $n\le 1000$;

4. ($15$ балів): $r_i\le 100$;

5. ($32$ бали): без додаткових обмежень.