Problema C - Ajudando os Concorrentes

Todos os anos, vários voluntários ajudam a organização das Olimpíadas esclarecendo dúvidas, fornecendo água para os concorrentes, entregando impressões e resolvendo todo o tipo de problemas que aparecem. Este ano não é excepção!

Por uma questão de organização os concorrentes estão dispostos numa grelha bidimensional, sendo que todos os voluntários se encontram inicialmente na posição (1,1). A figura seguinte ilustra uma possível posição inicial com dois voluntários (os smileys) e três concorrentes (os números):

Por vezes a meio de prova acumulam-se vários pedidos, que têm depois de ser atendidos exactamente pela ordem em que foram feitos. Felizmente, nunca surgem dois problemas exactamente em simultâneo! Como todos somos "preguiçosos", queremos atender esses pedidos percorrendo a mínima distância possivel, ou seja, queremos uma solução que implique que a soma das distâncias percorridas pelos voluntários seja a mínima possível. Para atender um pedido de ajuda de um concorrente, um voluntário desloca-se da sua posição actual para a posição do concorrente, permanecendo então nesse local até ter de atender novo pedido.

Para o exemplo dado anteriormente, imaginemos que os pedidos dos concorrentes chegam na seguinte ordem: 3, 2, 1, 2, 1. Dito de outro modo, primeiro temos de atender o concorrente 3, depois o concorrente 2, depois o concorrente 1, depois novamente o concorrente 2 e finalmente o concorrente 1 outra vez. Uma maneira possível de atender estes pedidos (por ordem!) seria a seguinte (onde a vermelho está indicado o pedido de ajuda actual):

Quando um voluntário se desloca de uma posição para outra não pode passar por cima dos concorrentes. Por isso mesmo, usa uns corredores que existem sempre entre duas célculas da grelha, fazendo com que ande sempre na vertical ou na horizontal. Formalmente, a distância percorrida para ir da posição (x1,y1) para a posição posição (x2,y2) é igual a |x1-x2| + |y1-y2|.

Usando esta definição, a soma das distâncias percorridas pelos voluntários na possível solução dada anteriormente seria de 13 (4+3+2+2+2). No entanto, é possível fazer melhor, como é exemplificado na figura a seguir, onde a soma das distâncias percorridas seria de 8 (4+3+1+0+0).

Podes ajudar-nos a calcular a distância mínima para um caso geral?

O Problema

Dado o número V de voluntários disponíveis (que começam sempre na posição (1,1)), um número C de concorrentes (e as suas respectivas posições), e um número P de pedidos de ajuda, a tua tarefa é dizer qual a distância mínima que os voluntários necessitam de percorrer para atender todos os pedidos de ajuda pela ordem em que foram feitos.

Só é necessário um voluntário para resolver cada problema e a distância total percorrida é igual à soma das distâncias individuais percorridas por cada voluntário.

Input

Na primeira linha do input vem um número V indicando o número de voluntários.

Segue-se uma linha com um único número N indicando o número de concorrentes, seguida de N linhas, cada uma contendo dois números X_i e Y_i (separados por um espaço) indicando a posição do i-ésimo concorrente (a primeira linha indica a posição do concorrente nº 1, a segunda o concorrente nº 2 e por aí adiante). Dois concorrentes diferentes nunca estarão na mesma posição.

Depois vem uma linha com um número P, indicando o número de pedidos, seguida de P linhas indicando os pedidos, pela ordem em que foram feitos, contendo cada uma destas linhas um único inteiro entre 1 e N indicando o número do concorrente que fez o respectivo pedido.

Output

O output deve ter exactamente uma linha, contendo um único inteiro correspondendo à distância mínima que os voluntários necessitam de percorrer.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 15% dos pontos, existirá apenas um voluntário.

Para um conjunto de casos de teste valendo 60% dos pontos, o número de pedidos será inferior ou igual a 10.

Exemplo de Input

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

Exemplo de Output

8