Cədvəl

"'markdown Son zamanlar Kozak Vus öz şirkətini qurdu. Şirkət çox sürətlə inkişaf edir və buna görə də artıq çoxlu işçisi var.

Kozak Vus işçilərinə $n$ tapşırıq verdi. Hər bir $i$-ci tapşırığın iki parametri var: $r_i$ və $c_i$. Burada $r_i$ $i$-ci tapşırığın yerinə yetirilməli olduğu vaxt anını, $c_i$ isə tapşırığın əhəmiyyətini göstərir (c_i nə qədər böyükdürsə, tapşırıq bir o qədər əhəmiyyətlidir).

Həmçinin, Kozak Vus müəyyən bir tam sabit $k$ təyin edib.

İşçilər $e$ adlı $n$ qeyri-mənfi ədədlərdən ibarət bir massiv tapmalıdırlar ki, aşağıdakı ifadə mümkün qədər kiçik olsun:

Burada $\max (e)$ $e$ massivinin maksimum ədədini göstərir.

Kozak Vus $e$ massivinin özünə maraq göstərmir. O, yuxarıda göstərilən ifadənin mümkün olan minimum dəyərini bilmək istəyir.

Kozak Vusun işçilərinə bu problemi həll etməyə kömək edin.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $k$ ($1\le n\le 10^6,0\le k\le 10^9$) — Kozak Vusun işçilərə verdiyi tapşırıqların sayı və şərtdəki sabit.

İkinci sətir $n$ tam ədəd $r_1,r_2,\dots ,r_n$ ($0\le r_i\le 10^6$) — $r$ massivi.

Üçüncü sətir $n$ tam ədəd $c_1,c_2,\dots ,c_n$ ($0\le c_i\le 10^6$) — $c$ massivi.

Çıxış verilənləri

Tək bir ədəd çıxarın — ifadənin mümkün olan minimum dəyəri ${\sum }_{i=1}^n|r_i-e_i|\cdot c_i+\max (e)\cdot k$.

Nümunələr

Qeyd

Birinci nümunədə minimum dəyərə çatılan $e$ massivi belə görünür: $[1,2,3]$. O zaman minimum dəyər $|1-1|\cdot 1+|2-2|\cdot 2+|3-3|\cdot 3+3\cdot 1=3$ bərabərdir.

İkinci nümunədə minimum dəyərə çatılan $e$ massivi belə görünür: $[0,0,0]$. O zaman minimum dəyər $|1-0|\cdot 3+|2-0|\cdot 2+|3-0|\cdot 1+0\cdot 100=10$ bərabərdir.

Üçüncü nümunədə minimum dəyərə çatılan $e$ massivi belə görünür: $[1,2,2]$. O zaman minimum dəyər $|1-1|\cdot 1+|2-2|\cdot 2+|3-2|\cdot 3+2\cdot 5=13$ bərabərdir.

Qiymətləndirmə

1. ($8$ bal): $c_i=0$;

2. ($15$ bal): $c_i=1$;

3. ($30$ bal): $n\le 1000$;

4. ($15$ bal): $r_i\le 100$;

5. ($32$ bal): əlavə məhdudiyyətlərsiz.

"'