En la olimpiada rusa de informática del año 2224, celebrada en Иннополис, las entregas las realizan robots de nueva generación capaces de crear clones de sí mismos. Las entregas se pueden recibir directamente por la ventana, sin salir de casa.
Inicialmente solo hay un robot repartidor. En cualquier momento, el robot situado más arriba puede crear uno o varios robots nuevos directamente encima de sí mismo. Así se forma una columna de robots. Cada robot tiene la altura de una planta.
Durante las entregas, la columna de robots clonados idénticos se desplaza de izquierda a derecha a lo largo de los edificios de las residencias. La base de datos de los robots contiene una lista de los pedidos realizados; para cada uno se conoce la ventana a la que debe entregarse. Cuando la columna pasa junto a la ventana de un pedido, puede entregarlo si hay un robot en la columna situado a la altura de esa ventana.
Durante el desplazamiento, la estructura de robots puede chocar con un obstáculo. Después del obstáculo, solo continúan moviéndose los robots que estaban por encima de él. Estos quedan en el suelo inmediatamente detrás del obstáculo, todavía formando una columna vertical, y pueden seguir desplazándose, crear nuevos clones y entregar pedidos.
La distancia entre los obstáculos y las ventanas es lo suficientemente grande como para que los robots no pasen junto a ninguna ventana mientras atraviesan un obstáculo.
Por entregar un pedido, la empresa organizadora recibe $p$ criptorublos. Crear un robot nuevo cuesta $c$ criptorublos. El beneficio final es el ingreso total por los pedidos entregados menos el coste total de crear todos los robots. La empresa quiere maximizar su beneficio. No está obligada a entregar todos los pedidos, y los robots pueden detenerse en cualquier momento y terminar el proceso de entrega.
Determina el beneficio máximo que puede obtener la empresa.
Entrada
La primera línea contiene cuatro enteros $n,m,c,p$ ($0 \le n,m \le 100000$, $1 \le c,p \le 10^6$): el número de obstáculos, el número de pedidos en la base de datos, el coste de crear un clon de robot y el precio de entregar un pedido, respectivamente.
Las siguientes $n+m$ líneas describen los obstáculos y las ventanas a las que deben entregarse pedidos, en el orden en que la columna los encuentra al desplazarse de izquierda a derecha a lo largo de las residencias. Cada línea contiene dos enteros $t_i$ y $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$). El tipo del objeto es $t_i$ ($1$ para un obstáculo y $2$ para una ventana), y $h_i$ es la altura del obstáculo en plantas o la planta en la que está situada la ventana.
Se garantiza que exactamente $n$ objetos son de tipo $1$ y los $m$ objetos restantes son de tipo $2$.
Salida
Imprime un número: el beneficio máximo que se puede obtener.
Subtareas
| Subtarea | Puntos | Restricción sobre $n$ | Restricción sobre $m$ | Restricciones adicionales | Subtareas necesarias |
|---|---|---|---|---|---|
| $1$ | $24$ | $n \le 100$ | $m \le 100$ | $h_i \le 100$ | |
| $2$ | $12$ | $n=0$ | |||
| $3$ | $14$ | $n=1$ | |||
| $4$ | $15$ | $m=1$ | |||
| $5$ | $17$ | $c=1$, $p=10^6$; todos los obstáculos tienen altura $1$ | |||
| $6$ | $18$ | Ejemplos, $1$–$5$ |
Ejemplos
Entrada 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Salida 1
4
Entrada 2
1 3 1 5 2 2 2 1 1 9 2 1
Salida 2
9
Nota
Una de las estrategias óptimas para entregar los pedidos del primer ejemplo se muestra en los nueve dibujos siguientes. Entregar el segundo pedido no aumenta el beneficio.
En el segundo ejemplo basta con clonar el robot una vez para entregar el primer pedido y entregar el segundo pedido con el sistema de robots resultante. Realizar más clonaciones para entregar el tercer pedido no resulta económicamente rentable.