Ənənəvi Oyun

Bir neçə il əvvəl, Chmyaaax hələ pis olmadıqda, o, Antonla Link-Cut planet sisteminin tayfalarından olan ənənəvi oyunu oynamağı sevirdi. Oyun $1\times n$ lövhəsində baş verir, burada hər bir hüceyrədə $a_i,b_i$ cüt ədədi var, bütün ədədlər fərqlidir. Həmçinin, başlanğıcda $1$-ci mövqedə olan bir oyun parçası və başlanğıcda $0$ olan sehrli bir balans var. Oyunçular növbə ilə hərəkət edirlər, Chmyaaax birinci başlayır.

Tutaq ki, oyun parçası hazırda $i$ hüceyrəsindədir.

1. Chmyaaax növbəsində parçasını $k$ hüceyrə irəlilədə bilər, burada $k>0$, balansdan $k\cdot a_i$ qəpik çıxararaq, parçasının mövqeyini $i+k$-ə dəyişdirir.

2. Anton növbəsində parçasını $k$ hüceyrə geri apara bilər, burada $k>0$, balansa $k\cdot b_i$ qəpik əlavə edərək, parçasının mövqeyini $i-k$-ə dəyişdirir, ya da sehrdən istifadə edərək parçasını son hüceyrəyə aparır, balansı $(n-i)\cdot b_i$ qəpik artıraraq, parçasını $n$ mövqeyinə qoyur.

Hər hansı bir vaxtda, parça lövhədən kənara çıxa bilməz (yəni, onun mövqeyi 0-dan böyük və $n+1$-dən kiçik olmalıdır). Oyun parça $n$ hüceyrəsinə çatdıqda bitir. Chmyaaaxın məqsədi balansı maksimuma çatdırmaqdır, Antonun məqsədi isə balansı minimuma endirməkdir. Hər iki oyunçu optimal oynasa, oyunun sonunda balans nə olacaq? Bu şərtlər altında oyunun sonsuz davam etməyəcəyi sübut oluna bilər.

Giriş verilənləri

Birinci sətir bir tam ədəd $n(2\le n\le 10^6)$ - oyunun baş verdiyi lövhənin ölçüsünü ehtiva edir.

İkinci sətir $n$ tam ədəd $a_i(-10^9\le a_i\le 10^9)$ ehtiva edir.

Üçüncü sətir $n$ tam ədəd $b_i(-10^9\le b_i\le 10^9)$ ehtiva edir.

Hər bir $i$ və $j$ cütü üçün, belə ki, $i\ne j$ və $1\le i,j\le n$, $a_i\ne a_j$, $b_i\ne b_j$ və $a_i\ne b_j$ şərtləri ödənilir.

Çıxış verilənləri

Hər iki oyunçu optimal oynasa, oyunun sonunda balansın dəyərini çıxarmalısınız.

Nümunələr

Qeyd

Birinci test nümunəsində, Chmyaaax üçün optimaldır ki, başlanğıcdan sona qədər atlayaraq balansı $33\cdot 7=231$ azaltsın, balansı $-231$ əldə etsin. Onun üçün daha böyük balans əldə etməyə imkan verən heç bir strategiya olmadığı sübut oluna bilər.

İkinci test nümunəsində, Chmyaaax $2$-ci hüceyrəyə atlayaraq balansı $-5\cdot 2=-10$ dəyişdirə bilər, Anton parçasını son hüceyrəyə apararaq balansı $15\cdot 2=30$ artıraraq balansı $20$ edər.

Qiymətləndirmə

1. ($25$ xal): $n\le 20$;

2. ($30$ xal): $n\le 50$, $-200\le a_i,b_i\le 200$;

3. ($40$ xal): $n\le 5000$;

4. ($30$ xal): $n\le 10^5$;

5. ($75$ xal): əlavə məhdudiyyət yoxdur.