Нещодавно Козак Вус заснував власну компанію. Компанія дуже стрімко розвивається, а тому вже має багато працівників.
Козак Вус поставив своїм працівникам n задач. i-та задача має два параметри: ri та ci. ri — момент часу, коли i-та задача повинна бути виконаною. ci — важливість задачі (чим більше ci, тим більш важлива задача).
Також Козак Вус задав деяку цілу сталу k.
Працівникам треба знайти такий масив e з n невід'ємних чисел, щоб наступне число було мінімально можливим:
max(e) — максимальне число масиву e.
Козака Вуса не цікавить сам масив e. Він хоче дізнатися зазначене вище мінімальне можливе значення.
Допоможіть працівникам Козака Вуса розв'язувати цю задачу.
Перший рядок містить два цілі числа n та k (1≤n≤106,0≤k≤109) — кількість задач, які поставив Козак Вус працівникам, та стала з умови.
Другий рядок містить n цілих чисел r1,r2,…,rn (0≤ri≤106) — масив r.
Третій рядок містить n цілих чисел c1,c2,…,cn (0≤ci≤106) — масив c.
Виведіть єдине число — мінімальне можливе значення виразу ∑i=1n∣ri−ei∣⋅ci+max(e)⋅k.
У першому прикладі масив e при якому досягається мінімальне значення виглядає так: [1,2,3]. Тоді мінімальне значення дорівнює ∣1−1∣⋅1+∣2−2∣⋅2+∣3−3∣⋅3+3⋅1=3.
У другому прикладі масив e при якому досягається мінімальне значення виглядає так: [0,0,0]. Тоді мінімальне значення дорівнює ∣1−0∣⋅3+∣2−0∣⋅2+∣3−0∣⋅1+0⋅100=10.
У третьому прикладі масив e при якому досягається мінімальне значення виглядає так: [1,2,2]. Тоді мінімальне значення дорівнює ∣1−1∣⋅1+∣2−2∣⋅2+∣3−2∣⋅3+2⋅5=13.
(8 балів): ci=0;
(15 балів): ci=1;
(30 балів): n≤1000;
(15 балів): ri≤100;
(32 бали): без додаткових обмежень.