joc

Jocul preferat al lui Aurel are o hartă împărțită în $N$ sectoare, numerotate, în ordine, de la $1$ la $N$. Fiecare sector $i$ ($1 \leq i \leq N$) are asociate două numere naturale reprezentând un decor, $decor_i$ și un scor, $scor_i$. Două decoruri de același tip sunt codificate prin același număr natural.

O secvență formată din $lg$ ($lg \ge 2$) sectoare aflate pe poziții consecutive este numită riscantă dacă cel puțin $\frac{lg}{2}+1$ dintre sectoarele acesteia au asociat același tip de decor, unde $\frac{lg}{2}$ reprezintă câtul împărțirii lui $lg$ la 2.

Dacă Aurel se află pe sectorul $s$ și are vizibilitatea $v$ ($0 \leq v \leq s-1$), el va "vedea" pe hartă secvența de $v+1$ sectoare consecutive, care se încheie cu $s$: $s-v, s-v+1, \dots, s$.

La începutul jocului, Aurel este poziționat într-un anumit sector (sector de start) și are o anumită vizibilitate. La fiecare pas al jocului, Aurel, fiind poziționat într-un sector oarecare, efectuează una dintre acțiunile:

• dacă secvența pe care o "vede" pe hartă este riscantă, Aurel scade cu $1$ vizibilitatea pe care o are (astfel el speră ca secvența rezultată să nu mai fie riscantă);
• dacă secvența pe care o "vede" pe hartă nu este riscantă, Aurel avansează, poziționându-se în sectorul următor, și crește cu 1 vizibilitatea (el se simte încurajat și merge mai departe).

Jocul se termină când el iese de pe hartă, adică se află după sectorul cu numărul $N$ (ultimul).

Scorul obținut este egal cu suma scorurilor sectoarelor în care el a fost poziționat la fiecare pas pe parcursul jocului (inclusiv scorul sectorului de start).

Cerință

• Determinați numărul de moduri în care Aurel poate începe jocul, astfel încât prima secvență pe care o "vede" pe hartă să NU fie riscantă. Două moduri de a începe jocul sunt considerate diferite dacă încep pe sectoare diferite sau dacă au vizibilitatea diferită.
• Determinați scorul obținut dacă Aurel pornește din sectorul $1$ cu vizibilitatea $0$.

Date de intrare

Fișierul de intrare joc.in conține pe prima linie numărul natural $C$ reprezentând cerința care trebuie să fie rezolvată. Pe a doua linie se află numărul natural $N$ reprezentând numărul de sectoare. Pe a treia linie se află $N$ numere naturale, reprezentând decorurile asociate sectoarelor, în ordinea numerotării acestora. Pe a patra linie se află $N$ numere naturale, reprezentând scorurile asociate sectoarelor, în ordinea numerotării acestora. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire joc.out conține o singură linie pe care este scris numărul determinat pentru cerința $C$ din fișierul de intrare.

Restricții și precizări

• $1 \leq C \leq 2$
• Dacă $C=1$, atunci $1 \leq N \leq 3 \ 000$
• Dacă $C=2$, atunci $1 \leq N \leq 100 \ 000$
• $1 \leq decor_i \leq N$, pentru $1 \leq i \leq N$
• $1 \leq scor_i \leq 1 \ 000 \ 000$, pentru $1 \leq i \leq N$

Exemplul 1

joc.in

1
5
1 1 2 1 3
2 3 1 1 5

joc.out

10

Explicație

Se notează cu $st$ sectorul de start și cu $v$ vizibilitatea; există $10$ moduri în care Aurel poate începe jocul astfel încât prima secvență văzută să nu fie riscantă:

• $st=1$, $v=0$ (secvența $1$)
• $st=2$, $v=0$ (secvența $2$)
• $st=3$, $v=0$ (secvența $3$)
• $st=4$, $v=0$ (secvența $4$)
• $st=5$, $v=0$ (secvența $5$)
• $st=3$, $v=1$ (secvența $2,3$)
• $st=4$, $v=1$ (secvența $3,4$)
• $st=5$, $v=1$ (secvența $4,5$)
• $st=5$, $v=2$ (secvența $3,4,5$)
• $st=5$, $v=3$ (secvența $2,3,4,5$)

Exemplul 2

joc.in

2
5
1 1 2 1 3
2 3 1 1 5

joc.out

16

Explicație

Aurel pornește din sectorul $1$ cu vizibilitate $v=0$. Scorul total este inițial $scor_1=2$.

• El vede doar sectorul $1$, iar secvența văzută nu este riscantă, deci avansează în sectorul $2$ și crește $v$ cu $1$. La scorul total se adună $scor_2=3$.
• Secvența văzută, formată din sectoarele $1,2$, este riscantă, deci scade $v$ cu $1$. Aurel este acum în sectorul $2$, cu $v=0$. La scorul total se adună $scor_2=3$.
• Secvența curentă văzută nu este riscantă, deci avansează în sectorul $3$ și crește $v$ cu $1$. La scorul total se adună $scor_3=1$.
• Secvența văzută $2,3$ nu este riscantă, deci avansează în sectorul $4$ și crește $v$ cu $1$. La scorul total se adună $scor_4=1$.
• Secvența văzută, formată din sectoarele $2,3,4$ este riscantă, deci scade $v$ cu $1$. La scorul total se adună $scor_4=1$.
• Secvența văzută $3,4$ nu este riscantă, deci avansează în sectorul $5$ și crește $v$ cu $1$. La scorul total se adună $scor_5=5$.
• Secvența văzută formată din sectoarele $3,4,5$ nu este riscantă, deci avansează și se poziționează după ultimul sector, terminând jocul. Scorul total obținut este $2+3+3+1+1+1+5=16$.