A Ilha JOI é composta por $L$ distritos, numerados de $1$ a $L$ de oeste para leste. A ilha tem $L-1$ estradas, numeradas de $1$ a $L-1$. A estrada $i$ ($1 \le i \le L-1$) liga os distritos $i$ e $i+1$ nos dois sentidos.

Está previsto que a Olimpíada Internacional de Informática (IOI 20XX) seja realizada na Ilha JOI! A preocupação é que a ilha é famosa pelo seu calor extremo. Existe um risco elevado de insolação, sobretudo para os participantes estrangeiros que não estão habituados a ambientes quentes. Por isso, os organizadores da IOI decidiram tomar as seguintes medidas:

• Primeiro, para cada $i$ ($1 \le i \le L$), preparam um hospital no distrito $i$ com capacidade para $C_i$ pessoas. Note que pode ocorrer $C_i=0$.
• Durante o evento da IOI, quando uma pessoa sofre uma insolação na estrada $x$ ($1 \le x \le L-1$), é enviada para um hospital através do seguinte procedimento:
  • O paciente é enviado para o hospital do distrito $x$ ou do distrito $x+1$, escolhendo um que não esteja cheio. Se nenhum dos dois estiver cheio, qualquer escolha é permitida. Se ambos estiverem cheios, o paciente é enviado de helicóptero para um hospital geral fora da ilha.

Como o uso de helicópteros é dispendioso, os organizadores querem estimar o número máximo de pacientes que serão transportados de helicóptero. Consideram o seguinte cenário como exemplo:

• Antes do evento da IOI, não há pacientes em nenhum hospital.
• Durante o evento da IOI, $N$ pessoas sofrerão uma insolação na Ilha JOI. O $j$-ésimo paciente ($1 \le j \le N$) surge na estrada $X_j$.
• Para cada $j$ ($1 \le j \le N-1$), quando o $(j+1)$-ésimo paciente sofre uma insolação, o $j$-ésimo paciente e todos os anteriores já foram enviados para um hospital. Devido à gravidade dos sintomas da insolação, nenhum paciente recebe alta durante o evento da IOI.

Escreva um programa que, dado o número de distritos e as informações sobre os hospitais e os pacientes com insolação, calcule o número máximo de pacientes que serão transportados de helicóptero no cenário acima.

Entrada

Leia os seguintes dados da entrada padrão:

$$ \begin{array}{l} L\\ C_1\ C_2\ \cdots\ C_L\\ N\\ X_1\ X_2\ \cdots\ X_N \end{array} $$

Saída

Escreva uma linha na saída padrão, contendo o número máximo de pacientes que serão transportados de helicóptero.

Restrições

• $2 \le L \le 8\,000$.
• $0 \le C_i \le 8\,000$ ($1 \le i \le L$).
• $1 \le N \le 8\,000$.
• $1 \le X_j \le L-1$ ($1 \le j \le N$).
• Todos os valores dados são inteiros.

Subtarefas

1. ($6$ pontos) $X_1 \le X_2 \le \cdots \le X_N$.
2. ($7$ pontos) $L \le 18$, $N \le 18$, $C_i=1$ ($1 \le i \le L$).
3. ($7$ pontos) $L \le 18$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
4. ($25$ pontos) $L \le 100$, $N \le 100$, $C_i=1$ ($1 \le i \le L$).
5. ($25$ pontos) $L \le 100$, $N \le 100$.
6. ($10$ pontos) $L \le 600$, $N \le 600$.
7. ($15$ pontos) $L \le 3\,500$, $N \le 3\,500$.
8. ($5$ pontos) Sem restrições adicionais.

Exemplos

Entrada 1

3
1 1 1
3
1 2 2

Saída 1

1

Explicação

Se ocorrer o seguinte caso, $1$ paciente será transportado de helicóptero.

1. O primeiro paciente é enviado para o hospital do distrito $2$. Os números de pacientes nos hospitais dos distritos $1,2,3$ passam a ser, respetivamente, $0,1,0$.
2. O segundo paciente é enviado para o hospital do distrito $3$. Os números de pacientes nos hospitais dos distritos $1,2,3$ passam a ser, respetivamente, $0,1,1$.
3. Para o terceiro paciente, como os hospitais dos distritos $2$ e $3$ estão ambos cheios, o paciente é enviado de helicóptero para um hospital geral fora da ilha.

Como não existe nenhum caso em que $2$ ou mais pacientes sejam transportados de helicóptero, escreva $1$.

Esta entrada de exemplo satisfaz as restrições das subtarefas $1,2,3,4,5,6,7,8$.

Entrada 2

6
1 1 1 1 1 1
7
1 3 5 4 2 2 3

Saída 2

3

Explicação

Se ocorrer o seguinte caso, $3$ pacientes serão transportados de helicóptero.

1. O primeiro paciente é enviado para o hospital do distrito $2$. Os números de pacientes nos hospitais dos distritos $1,2,3,4,5,6$ passam a ser, respetivamente, $0,1,0,0,0,0$.
2. O segundo paciente é enviado para o hospital do distrito $4$. Os números de pacientes nos hospitais dos distritos $1,2,3,4,5,6$ passam a ser, respetivamente, $0,1,0,1,0,0$.
3. O terceiro paciente é enviado para o hospital do distrito $5$. Os números de pacientes nos hospitais dos distritos $1,2,3,4,5,6$ passam a ser, respetivamente, $0,1,0,1,1,0$.
4. Para o quarto paciente, como os hospitais dos distritos $4$ e $5$ estão ambos cheios, o paciente é enviado de helicóptero para um hospital geral fora da ilha.
5. O quinto paciente é enviado para o hospital do distrito $3$. Os números de pacientes nos hospitais dos distritos $1,2,3,4,5,6$ passam a ser, respetivamente, $0,1,1,1,1,0$.
6. Para o sexto paciente, como os hospitais dos distritos $2$ e $3$ estão ambos cheios, o paciente é enviado de helicóptero para um hospital geral fora da ilha.
7. Para o sétimo paciente, como os hospitais dos distritos $3$ e $4$ estão ambos cheios, o paciente é enviado de helicóptero para um hospital geral fora da ilha.

Como não existe nenhum caso em que $4$ ou mais pacientes sejam transportados de helicóptero, escreva $3$.

Esta entrada de exemplo satisfaz as restrições das subtarefas $2,3,4,5,6,7,8$.

Entrada 3

6
4000 1 1 0 4000 1
5
1 1 2 3 5

Saída 3

1

Explicação

Esta entrada de exemplo satisfaz as restrições das subtarefas $1,5,6,7,8$.

Entrada 4

5
1 2 2 2 1
8
2 3 2 1 4 1 2 3

Saída 4

2

Explicação

Esta entrada de exemplo satisfaz as restrições das subtarefas $5,6,7,8$.

Entrada 5

10
2 2 2 2 2 2 2 2 2 2
18
1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8

Saída 5

3

Explicação

Esta entrada de exemplo satisfaz as restrições das subtarefas $5,6,7,8$.