E. Pizarra
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Te has perdido por el instituto, y después de dar muchas vueltas acabas en una clase vacía, que contiene solamente un cartel y una pizarra con los números enteros a1, ..., an escritos en ella. En el cartel hay una lista de precios:

  • Por l euros, puedes borrar un número x de la pizarra y escribir x - 1.
  • Por r euros, puedes borrar un número x de la pizarra y escribir x + 1.
  • Gratuitamente, puedes duplicar un número de la pizarra (es decir, escribir una copia sin borrar el original).
Tienes unos cuantos números favoritos b1, ..., bm, y no puedes aguantar la irresistible tentación de conseguir que todos tus números favoritos aparezcan en la pizarra. Calcula el mínimo dinero que necesitarías para cumplir tu objetivo.
Input

La primera línea contiene un entero T, el número de casos. Siguen T casos, cada uno con 3 líneas:

  • La primera línea contiene n, m, l y r.
  • La segunda línea contiene los n enteros a1, ..., an escritos en la pizarra.
  • La tercera línea contiene tus m números favoritos b1, ..., bm.
Output

Para cada caso imprime en una línea un solo entero, el mínimo dinero que necesitas para que todos tus números favoritos aparezcan en la pizarra.

Scoring
  1. (7 puntos) m = 1.
  2. (12 puntos) n = 1.
  3. (6 puntos) l = 0.
  4. (16 puntos) l = 1, r = 106.
  5. (24 puntos) La suma de n sobre todos los casos es como mucho 1000. La suma de m sobre todos los casos es como mucho 1000.
  6. (24 puntos) l = r = 1.
  7. (11 puntos) Sin restricciones adicionales.
Example
Input
1
4 3 1 2
1 7 1 10
2 5 8
Output
6
Note
  • 1 ≤ T ≤ 105
  • La suma de n sobre todos los casos es como mucho 2·105
  • La suma de m sobre todos los casos es como mucho 2·105
  • 0 ≤ l, r ≤ 106
  • 1 ≤ ai ≤ 106 para todo 1 ≤ i ≤ n
  • 1 ≤ bi ≤ 106 para todo 1 ≤ i ≤ m
  • El array b no contiene números repetidos.