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 ≤ i ≤ N) are asociate două numere naturale reprezentând un decor, decori și un scor, scori. Două decoruri de același tip sunt codificate prin același număr natural.

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

Dacă Aurel se află pe sectorul s și are vizibilitatea v (0 ≤ v ≤ s-1), el va “vedea” pe hartă secvența de v+1 sectoare consecutive, care se încheie cu s: s-v, s-v+1, ... 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ț3

1) 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ă.
2) 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 va 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 ≤ C ≤ 2
• Dacă C = 1, atunci 1 ≤ N ≤ 3.000
• Dacă C = 2, atunci 1 ≤ N ≤ 100.000
• 1 ≤ decori ≤ N, pentru 1 ≤ i ≤ N
• 1 ≤ scori ≤ 1.000.000, pentru 1 ≤ i ≤ N
• Pentru 25 de puncte, C=1, 1 ≤ N ≤ 800
• Pentru 21 de puncte, C=1, 800 < N ≤ 3.000
• Pentru 24 de puncte, C=2, 1 ≤ N ≤ 9.000
• Pentru 30 de puncte, C=2, 9.000 < N ≤ 100.000

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 scor1 = 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ă scor2 = 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ă scor2 = 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ă scor3 = 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ă scor4 = 1.
• Secvența văzută, formată din sectoarele 2,3,4 este riscantă, deci scade v cu 1. La scorul total se adună scor4 = 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ă scor5 = 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.