A grande
cidade do Porto é um local cheio de história e
entretenimento. Para incentivar os residentes e turistas a
explorar a cidade, o metro do Porto lançou um jogo que consiste
em explorar os sítios mais emblemáticos da cidade andando sempre
de metro. O jogo consiste em andar entre diferentes estações
para ganhar pontos, tendo que gastar pontos para andar entre
estações. O objetivo é maximizar o número de pontos final.
Para os propósitos do jogo, podemos pensar no metro do Porto como uma linha com N estações. Cada estação pertence a uma de Z zonas, sendo que cada zona contém um intervalo contíguo de estações (não há "buracos" entre zonas). As zonas estão numeradas de 1 a Z do início para o fim da linha de estações (ou seja, a zona 1 aparece antes da zona 2, a zona 2 antes da 3, ...).
Cada estação tem um prémio em pontos associado (um inteiro positivo), que é recolhido quando visitamos a área envolvente, ou seja, quando saímos nessa estação (não basta passar por lá durante uma viagem entre duas outras estações). Nota também que só recebemos o prémio da primeira vez que visitamos a estação (uma segunda visita não dá direito a nenhum prémio adicional).
Para nos deslocarmos entre duas estações, temos de pagar um custo fixo de A pontos, ao qual somamos B pontos por cada zona que atravessarmos (se nos deslocarmos dentro da mesma zona pagamos mais B pontos, de uma para outra pagamos mais 2B pontos, ...). Os valores de A e B são sempre inteiro positivos. Por exemplo, se começarmos uma viagem numa estação na zona 2 e terminarmos numa estação das zona 5, pagamos A + 4B pontos. Depois de terminar uma viagem, podemos iniciar uma nova viagem partindo da estação onde terminamos.
O objetivo do jogo é, partindo de uma dada estação I, calcular a maior pontuação final possível, terminando numa qualquer estação à nossa escolha. Durante o jogo podemos ter uma pontuação negativa, desde que a pontuação final seja a maior possível. Nota que a melhor pontuação final é sempre positiva, visto que na pior das hipóteses recolhemos a pontuação da estação inicial I e terminamos imediatamente o nosso passeio, sem visitar qualquer outra estação.
Se tivermos, por exemplo, N = 8, A = 1, B = 2 e I = 1, para a seguinte configuração (zona 1: estações 1, 2 e 3; zona 2: estações 4, 5; zona 3: estações 6, 7 e 8):
A melhor pontuação possível de se obter no jogo é 16, que é obtida por exemplo seguindo as setas da imagem:
Dado um conjunto de N estações, a zona e o prémio associado a cada uma, assim como um custo de transporte A e B entre zonas e uma estação inicial I, calcular a melhor pontuação possível de obter num passeio segundo as condições do jogo.
Na primeira linha vêm quatro inteiros, N que representam o número de estações, A que representa o custo fixo por viagem, B que representa o custo entre zonas e I que representa a estação inicial.
Na segunda linha vêm N inteiros separados por espaços, representando o prémio de cada estação.
Na terceira linha vêm N inteiros separados por espaços, representando a zona de cada estação (esta sequência é sempre crescente, começando em 1 e terminando em Z).
O output é uma linha contendo apenas um inteiro, que representa a melhor pontuação possível de obter. Nota: para os casos de teste maiores, este valor pode exceder 231.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ N ≤ 100 000 | Número de estações | |
| 1 ≤ Ni ≤ 1 000 000 | Prémio de cada estação | |
| 1 ≤ Z ≤ N | Número de zonas | |
| 1 ≤ A, B ≤ 1 000 000 | Custo entre zonas | |
| 1 ≤ I ≤ N | Estação inicial |
Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 15 | I = 1; N ≤ 10; Ni, A, B ≤ 1 000 |
| 2 | 15 | I = 1; N ≤ 2 000 |
| 3 | 15 | N ≤ 2 000 |
| 4 | 15 | I = 1; Z ≤ 2 000 |
| 5 | 20 | I = 1 |
| 6 | 20 | - |
8 1 2 1 2 9 8 3 6 2 7 1 1 1 1 2 2 3 3 3
16
Este exemplo corresponde ao mencionado no enunciado.
10 42 13 9 58 65 78 66 44 308 400 360 393 326 1 1 1 2 2 3 3 3 4 5
1549