Cədvəl#10469

Cədvəl

2 saniyə

256 meqabayt

Asan

"'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}$ r_i və $c_{i}$ c_i. Burada $r_{i}$ r_i $i$ -ci tapşırığın yerinə yetirilməli olduğu vaxt anını, $c_{i}$ 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:

i = 1 \sum n ∣ r_{i} - e_{i} ∣ \cdot c_{i} + max (e) \cdot k =

\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

= |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

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ş

Birinci sətir iki tam ədəd $n$ və $k$ ( $1 \leq n \leq 1 0^{6}, 0 \leq k \leq 1 0^{9}$ 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}$ r_1, r_2, \dots, r_n ( $0 \leq r_{i} \leq 1 0^{6}$ 0 \le r_i \le 10^6) — $r$ massivi.

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

Çıxış

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$ \sum_{i=1}^{n} |r_i - e_i| \cdot c_i + \max(e) \cdot k.

Nümunələr

Nümunə 1

Nümunə 2

Nümunə 3

Qeyd

Birinci nümunədə minimum dəyərə çatılan $e$ massivi belə görünür: $[1, 2, 3]$ [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$ |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]$ [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$ |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]$ [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$ |1-1| \cdot 1 + |2-2| \cdot 2 + |3-2| \cdot 3 + 2 \cdot 5=13 bərabərdir.

Bal hesablama

( $8$ bal): $c_{i} = 0$ c_i = 0;
( $15$ bal): $c_{i} = 1$ c_i = 1;
( $30$ bal): $n \leq 1000$ n \le 1000;
( $15$ bal): $r_{i} \leq 100$ r_i \le 100;
( $32$ bal): əlavə məhdudiyyətlərsiz.