Aux Olympiades panrusses d'informatique de 2224, qui se déroulent à Иннополис, les livraisons sont assurées par des robots de nouvelle génération capables de créer leurs propres clones. On peut recevoir sa livraison directement par la fenêtre, sans sortir de chez soi.
Au départ, il n'y a qu'un seul robot livreur. À tout moment, le robot situé tout en haut peut créer un ou plusieurs nouveaux robots directement au-dessus de lui. Une colonne de robots se forme ainsi. La hauteur de chaque robot est égale à celle d'un étage.
Pendant la livraison, la colonne de robots clones identiques se déplace le long des bâtiments de la résidence universitaire, de gauche à droite. La base de données des robots contient la liste des commandes passées, avec, pour chacune, la fenêtre à laquelle elle doit être livrée. Lorsque la colonne passe devant une fenêtre correspondant à une commande, elle peut effectuer la livraison si un robot de la colonne se trouve à la hauteur de cette fenêtre.
Au cours du déplacement, l'assemblage de robots peut rencontrer un obstacle. Après l'obstacle, seuls les robots qui se trouvaient au-dessus de celui-ci poursuivent leur déplacement. Ils se retrouvent au sol juste derrière l'obstacle, toujours sous forme de colonne verticale, et peuvent continuer à se déplacer, à créer de nouveaux clones et à livrer des commandes.
La distance entre les obstacles et les fenêtres est suffisamment grande pour que les robots ne passent pas devant une fenêtre pendant le franchissement d'un obstacle.
Pour chaque commande livrée, l'entreprise qui organise les livraisons reçoit $p$ cryptoroubles. La création d'un nouveau robot coûte $c$ cryptoroubles. Le bénéfice final est égal au revenu total des livraisons, diminué du coût total de création de tous les robots. L'entreprise souhaite maximiser son bénéfice. Elle n'est pas obligée de livrer toutes les commandes, et les robots peuvent s'arrêter à tout moment et mettre fin aux livraisons.
Déterminez le bénéfice maximal que l'entreprise peut obtenir.
Entrée
La première ligne contient quatre entiers $n,m,c,p$ ($0 \le n,m \le 100000$, $1 \le c,p \le 10^6$) : respectivement le nombre d'obstacles, le nombre de commandes dans la base, le coût de création d'un clone de robot et le prix de livraison d'une commande.
Les $n+m$ lignes suivantes décrivent les obstacles et les fenêtres auxquelles les commandes doivent être livrées, dans l'ordre où la colonne de robots les rencontre le long de la résidence, de gauche à droite. Chaque ligne contient deux entiers $t_i$ et $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$) : $t_i$ est le type de l'objet ($1$ pour un obstacle et $2$ pour une fenêtre), et $h_i$ est la hauteur de l'obstacle en étages ou l'étage auquel se trouve la fenêtre.
Il est garanti qu'exactement $n$ objets sont de type $1$ et que les $m$ autres objets sont de type $2$.
Sortie
Affichez un nombre : le bénéfice maximal qu'il est possible d'obtenir.
Sous-tâches
| Sous-tâche | Points | Contraintes sur $n$ | Contraintes sur $m$ | Contraintes supplémentaires | Sous-tâches requises |
|---|---|---|---|---|---|
| 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$ ; tous les obstacles ont une hauteur de $1$ | |||
| 6 | 18 | Exemples, 1–5 |
Exemples
Entrée 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Sortie 1
4
Entrée 2
1 3 1 5 2 2 2 1 1 9 2 1
Sortie 2
9
Remarque
L'une des stratégies optimales pour livrer les commandes du premier exemple est représentée dans les neuf dessins ci-dessous. Livrer la deuxième commande n'augmente pas le bénéfice.
Dans le deuxième exemple, il suffit de cloner le robot une fois pour livrer la première commande, puis de livrer la deuxième commande avec le système de robots ainsi obtenu. Effectuer des clonages supplémentaires pour livrer la troisième commande n'est pas économiquement avantageux.