Problema C - Jogo de Cartas

Vamos considerar alguns jogos jogados com dois baralhos de cartas especiais. Há dois baralhos de cartas, cada um com exatamente N cartas que têm um certo valor (um inteiro positivo) e estão numa certa ordem. O primeiro baralho é o baralho A e a i-ésima carta deste baralho vale exatamente A_i. O segundo baralho é o baralho B e a i-ésima carta deste baralho vale exatamente B_i. Os baralhos satisfazem ainda a seguinte propriedade: o valor de cada carta do baralho A é menor ou igual ao valor da carta equivalente do baralho B, ou por outras palavras, para todo o i temos que A_i ≤ B_i.

Parte I

Com estes baralhos podemos jogar vários jogos, vamos ver um muito simples. É nos dado um inteiro positivo X, o valor objetivo. Queremos formar pares de cartas onde uma carta vem do baralho A e outra do baralho B. Um par é válido se a soma dos valores das cartas for um múltiplo de X. O objetivo deste jogo é determinar quantos pares válidos existe.

Exemplo

Se N = 4, X = 3 e tivermos os seguintes baralhos:

• A = [1, 4, 6, 2]
• B = [1, 5, 6, 5]

Temos então os seguintes 6 pares válidos: (1, 5), (1, 5), (4, 5), (4, 5), (6, 6), (2, 1), onde cada (a, b) é um par de valores onde a vem do baralho A e b do baralho B. Logo a resposta é 6.

A seguinte figura ilustra este caso, onde as cartas azuis são as do primeiro baralho e as verdes as do segundo:

Restrições:

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

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Parte II

Um outro jogo que podemos jogar com estes baralhos funciona da seguinte forma. É nos dado um inteiro positivo X, o valor de salto. O objetivo do jogo é transformar o baralho A no baralho B o mais rapidamente possível. Para isso podemos fazer a seguinte operação: escolhemos um qualquer intervalo [s, e], onde s e e são inteiros entre 1 e N. De seguida, somamos X a cada carta neste intervalo, ou seja, cada valor A_i onde s ≤ i ≤ e passa a A_i + X.

Podemos fazer quantas operações quanto quisermos, mas no final o baralho A tem de ser igual ao baralho B, ou seja, para todo o i queremos que A_i = B_i. O objetivo do jogo é calcular o mínimo número de operações que são necessárias ou determinar que é impossível transformar A em B.

Exemplo

Se N = 4, X = 2 e tivermos os seguintes baralhos:

• A = [1, 4, 4, 2]
• B = [1, 8, 6, 6]

Precisamos apenas de três operações:

• [2, 4], o que resulta em A = [1, 6, 6, 4]
• [2, 2], o que resulta em A = [1, 8, 6, 4]
• [4, 4], o que resulta em A = [1, 8, 6, 6]

Restrições:

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

Os casos de teste desta parte do problema estão organizados em 2 grupos com restrições adicionais diferentes:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 4 grupos com restrições adicionais diferentes:

Input

Nota: O formato de input é igual para todas as partes.

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com dois inteiros separados por espaços, primeiro N, representando o número de cartas em cada baralho, seguido de X, o valor objetivo ou de salto (dependendo da parte).

Seguem-se duas linhas, cada uma contendo N inteiros separados por espaços. A primeira linha representa o baralho A, e a ordem do input é a ordem do baralho. A segunda linha representa o baralho B, e a ordem do input é a ordem do baralho.

Output

O output deve conter uma linha com um inteiro representando a resposta ao caso de teste:

• Parte I: o número de pares válidos;
• Parte II: o menor número de operações necessárias ou -1 caso não seja possível transformar A em B;

Input do Exemplo 1

1
4 3
1 4 6 2
1 5 6 5

Output do Exemplo 1

6

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo da Parte I mencionado no enunciado.

Input do Exemplo 2

2
4 2
1 4 4 2
1 8 6 6

Output do Exemplo 2

3

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo da Parte II mencionado no enunciado.