Alle Olimpiadi russe di informatica del 2224, che si svolgono a Иннополис, le consegne sono effettuate da robot di nuova generazione capaci di creare cloni di sé stessi. Si può ricevere una consegna direttamente dalla finestra, senza uscire di casa.
Inizialmente esiste un solo robot addetto alle consegne. In qualsiasi momento, il robot più in alto può creare uno o più nuovi robot direttamente sopra di sé. Si forma così una colonna di robot. L'altezza di ciascun robot è pari all'altezza di un piano.
Durante le consegne, la colonna di robot-cloni identici si sposta da sinistra a destra lungo gli edifici del dormitorio. La banca dati dei robot contiene un elenco degli ordini effettuati, per ciascuno dei quali è nota la finestra alla quale deve essere consegnato. Quando la colonna passa davanti alla finestra corrispondente a un ordine, può effettuare la consegna se nella colonna c'è un robot all'altezza della finestra.
Durante lo spostamento, la struttura di robot può incontrare un ostacolo. Dopo l'ostacolo, continuano a muoversi soltanto i robot che si trovavano al di sopra dell'ostacolo. Essi si ritrovano a terra immediatamente dopo l'ostacolo, ancora disposti in una colonna verticale, e possono continuare a spostarsi, creare nuovi cloni e consegnare gli ordini.
La distanza tra gli ostacoli e le finestre è sufficientemente grande, quindi durante il superamento di un ostacolo i robot non passano davanti a una finestra.
Per la consegna di un ordine, l'azienda che organizza le consegne riceve $p$ criptorubli. Il costo per creare un nuovo robot è di $c$ criptorubli. Il profitto finale è pari al ricavo complessivo delle consegne meno il costo complessivo della creazione di tutti i robot. L'azienda vuole massimizzare il proprio profitto. Non è obbligata a soddisfare tutti gli ordini, e i robot possono fermarsi in qualsiasi momento e interrompere le consegne.
Determinate il massimo profitto che l'azienda può ottenere.
Input
La prima riga dell'input contiene quattro interi $n,m,c,p$ $(0 \le n,m \le 100000,\ 1 \le c,p \le 10^6)$: rispettivamente, il numero di ostacoli, il numero di ordini nella banca dati, il costo per creare un clone di robot e il prezzo della consegna di un ordine.
Le successive $n+m$ righe descrivono gli ostacoli e le finestre alle quali consegnare gli ordini, nell'ordine in cui la colonna di robot li incontra spostandosi da sinistra a destra lungo i dormitori. Ogni riga contiene due interi $t_i$ e $h_i$ $(1 \le t_i \le 2,\ 1 \le h_i \le 10^6)$: $t_i$ è il tipo di oggetto ($1$ per un ostacolo e $2$ per una finestra), e $h_i$ è l'altezza dell'ostacolo in piani oppure il piano al quale si trova la finestra.
È garantito che esattamente $n$ oggetti siano di tipo $1$ e che i restanti $m$ oggetti siano di tipo $2$.
Output
Stampate un solo numero: il massimo profitto ottenibile.
Sottoproblemi
| Sottoproblema | Punti | Vincoli su $n$ | Vincoli su $m$ | Vincoli aggiuntivi | Sottoproblemi richiesti |
|---|---|---|---|---|---|
| $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$; le altezze di tutti gli ostacoli sono uguali a $1$ | |||
| $6$ | $18$ | Esempi, $1$–$5$ |
Esempi
Input 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Output 1
4
Input 2
1 3 1 5 2 2 2 1 1 9 2 1
Output 2
9
Spiegazione
Una delle strategie ottimali per consegnare gli ordini del primo esempio è illustrata nelle nove figure seguenti; soddisfare il secondo ordine non aumenta il profitto.
Nel secondo esempio è sufficiente clonare il robot una sola volta per consegnare il primo ordine, quindi consegnare il secondo ordine con il sistema di robot ottenuto; effettuare ulteriori clonazioni per consegnare il terzo ordine non è economicamente conveniente.