Sıra

ABT ("Amortized Binary Trees") bazarında, $n$ müştəri $1$ ilə $n$ mövqelər arasında sıradadır. Kassirin $i$-ci müştərisini xidmət etmək üçün lazım olan vaxt $t_i$-dir.

Müştəri sırasında durmaq üçün lazım olan vaxt, onlardan əvvəlki bütün müştərilərin xidmət etmək üçün lazım olan vaxtların cəmi ilə bu müştəriyə xidmət etmək üçün lazım olan vaxtın cəmidir. Yəni, $t=[1,4,2]$ olan 3 nəfərlik bir sıradakı vaxtlar hər bir şəxs üçün hər biri aşağıdakı vaxtlardır: $1$, $1+4=5$ və $1+4+2=7$.

Müştərilərin xidmət görmədən əvvəl sıradakı vaxtların cəmini minimuma endirmək üçün, onlar yenidən sıralanmağa razı oldular. Lakin, $i$-ci müştəri öz orijinal mövqeyindən geri çəkilmək istəmir (amma, ətrafına hər hansı bir sayda üçün irəli getməkdə məsələ yoxdur). Bu müştərilər hansı minimum cəmi vaxtlarla nəticələnə bilərlər?

Giriş verilənləri

Birinci sətir, sıradakı müştərilərin sayını təyin edir. $(1\le n\le 10^5)$

İkinci sətir, hər bir müştəri üçün kassirin xidmət etmək üçün lazım olan vaxtı təyin edir. $(1\le t_i\le 10^9)$

Üçüncü sətir, hər bir müştəri üçün geri çəkilməyə razı olduğu maksimum mövqe sayını təyin edir. $(0\le a_i\le n-i)$

Çıxış verilənləri

Yalnız bir sətirdə, ən az sıra gözləmə vaxtlarının minimal cəmini çıxarın.

Nümunələr

Qeyd

Birinci nümunədə müştəriləri yenidən təşkil etməyin iki etibarlı yolu var:

1. $1$-st, $2$-nd və $3$-rd biri (heç kəsi yerindən tərpətmir);

2. $2$-ci, $1$-ci və $3$-ci;

3. $2$-ci, $3$-ci və $1$-ci;

4. $3$-ci, $2$-ci və $1$-ci.

Bu hallarda vaxtların cəmi:

1. $2+(2+4)+(2+4+1)=2+6+7=15$;

2. $4+(4+2)+(4+2+1)=17$;

3. $4+(4+1)+(4+1+2)=16$;

4. $1+(1+4)+(1+4+2)=13$.

Gördüyümüz kimi burada ən yaxşı cavab $13$-dır. Göstərilə bilər ki, bu növbədə insanların başqa mümkün tənzimləmələri yoxdur.

İkinci nümunədə, hər iki insan hər hansı bir mövqedə ola bilər, beləliklə onların hər iki mövcud sıralaması da səhihdir və onlar eyni cavab olan $1+(1+1)=3$-ü verirlər.

Üçüncü nümunədə, heç bir insanı hər hansı bir mövqedə hərəkət etməyəcəyinizi göstərmək mümkündür və onların yeganə səhih sıralaması əvvəlki sıradır. İnsanların bu sıradakı gözləmə vaxtlarının cəmi $1+3+6+10+15=35$ olacaqdır.