Na Olimpíada Russa de Informática de 2224, realizada em Иннополис, as entregas são feitas por robôs de nova geração capazes de criar clones de si mesmos. As entregas podem ser recebidas diretamente pela janela, sem sair de casa.
Inicialmente, existe apenas um robô entregador. A qualquer momento, o robô no topo pode criar um ou mais novos robôs diretamente acima de si. Assim se forma uma coluna de robôs. A altura de cada robô é igual à altura de um andar.
Durante as entregas, a coluna de robôs clones idênticos move-se ao longo dos edifícios dos dormitórios, da esquerda para a direita. A base de dados dos robôs contém uma lista de pedidos, e para cada pedido é conhecida a janela em que deve ser entregue. Quando a coluna de robôs passa por uma janela correspondente a algum pedido, pode fazer a entrega se houver na coluna um robô ao nível dessa janela.
Durante o movimento, a estrutura de robôs pode encontrar um obstáculo. Depois do obstáculo, apenas os robôs que estavam acima dele continuam a mover-se. Eles ficam no chão imediatamente após o obstáculo, ainda formando uma coluna vertical, e podem continuar a mover-se, criar novos clones e entregar pedidos.
A distância entre obstáculos e janelas é suficientemente grande, de modo que os robôs não passam por nenhuma janela enquanto atravessam um obstáculo.
Por cada pedido entregue, a empresa que organiza as entregas recebe $p$ criptorublos. O custo de criar um novo robô é $c$ criptorublos. O lucro final é a receita total das entregas menos o custo total de criação de todos os robôs. A empresa quer maximizar o seu lucro. Não é obrigada a entregar todos os pedidos, e os robôs podem parar a qualquer momento e encerrar o processo de entrega.
Determine o lucro máximo que a empresa pode obter.
Entrada
A primeira linha da entrada contém quatro inteiros $n$, $m$, $c$ e $p$ ($0 \le n,m \le 100000$, $1 \le c,p \le 10^6$): o número de obstáculos, o número de pedidos na base de dados, o custo de criar um clone de robô e o valor recebido pela entrega de um pedido, respetivamente.
As próximas $n+m$ linhas descrevem os obstáculos e as janelas onde os pedidos devem ser entregues, na ordem em que a coluna de robôs os encontra ao longo dos dormitórios, da esquerda para a direita. Cada linha contém dois inteiros $t_i$ e $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$): o tipo do objeto $t_i$ ($1$ para um obstáculo e $2$ para uma janela) e $h_i$, a altura do obstáculo em andares ou o andar em que a janela se encontra.
É garantido que exatamente $n$ objetos têm o tipo $1$, e os restantes $m$ objetos têm o tipo $2$.
Saída
Imprima um número: o lucro máximo que pode ser obtido.
Subtarefas
| Subtarefa | Pontos | Restrição sobre $n$ | Restrição sobre $m$ | Restrições adicionais | Subtarefas necessárias |
|---|---|---|---|---|---|
| 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$; as alturas de todos os obstáculos são iguais a $1$ | |||
| 6 | 18 | Exemplos, 1–5 |
Exemplos
Entrada 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Saída 1
4
Entrada 2
1 3 1 5 2 2 2 1 1 9 2 1
Saída 2
9
Nota
Uma das estratégias ótimas para entregar os pedidos do primeiro exemplo é ilustrada nas nove figuras abaixo; entregar o segundo pedido não aumenta o lucro.
No segundo exemplo, basta clonar o robô uma vez para entregar o primeiro pedido e usar a estrutura de robôs resultante para entregar o segundo pedido; fazer clonagens adicionais para entregar o terceiro pedido não é economicamente vantajoso.