Vid den allryska informatikolympiaden år 2224, som hålls i Иннополис, sköts leveranserna av en ny generation robotar som kan skapa kloner av sig själva. En leverans kan tas emot direkt genom fönstret, utan att man behöver lämna hemmet.
Från början finns bara en leveransrobot. När som helst kan den översta roboten skapa en eller flera nya robotar direkt ovanför sig. På så sätt bildas en kolonn av robotar. Varje robot är lika hög som en våning.
Under leveranserna rör sig kolonnen av identiska robotkloner från vänster till höger längs studentbostädernas byggnader. Robotarnas databas innehåller en lista över beställningar, och för varje beställning är det känt till vilket fönster den ska levereras. När robotkolonnen passerar ett fönster som motsvarar en beställning kan den utföra leveransen om det finns en robot i kolonnen på samma höjd som fönstret.
Under förflyttningen kan robotkonstruktionen stöta på ett hinder. Efter hindret fortsätter endast de robotar som befann sig ovanför hindret. De hamnar på marken direkt efter hindret, fortfarande i en lodrät kolonn, och kan fortsätta röra sig, skapa nya kloner och leverera beställningar.
Avståndet mellan hinder och fönster är tillräckligt stort för att robotarna inte ska passera något fönster medan de tar sig över ett hinder.
För att leverera en beställning får företaget som organiserar leveranserna $p$ kryptorubel. Kostnaden för att skapa en ny robot är $c$ kryptorubel. Den slutliga vinsten är den sammanlagda inkomsten från levererade beställningar minus den sammanlagda kostnaden för att skapa alla robotar. Företaget vill maximera sin vinst. Det behöver inte utföra alla beställningar, och robotarna kan när som helst stanna och avsluta leveransprocessen.
Bestäm den största vinst som företaget kan få.
Indata
Den första raden innehåller fyra heltal $n$, $m$, $c$, $p$ ($0 \le n,m \le 100\,000$, $1 \le c,p \le 10^6$): antalet hinder, antalet beställningar i databasen, kostnaden för att skapa en robotklon respektive ersättningen för att leverera en beställning.
De följande $n+m$ raderna beskriver hindren och de fönster till vilka beställningar ska levereras, i den ordning robotkolonnen passerar dem längs studentbostäderna från vänster till höger. Varje rad innehåller två heltal $t_i$ och $h_i$ ($1 \le t_i \le 2$, $1 \le h_i \le 10^6$): objektets typ $t_i$ ($1$ för ett hinder och $2$ för ett fönster), och $h_i$, som är hindrets höjd i våningar eller den våning där fönstret finns.
Det garanteras att exakt $n$ objekt har typ $1$ och att de återstående $m$ objekten har typ $2$.
Utdata
Skriv ut ett tal: den största vinst som kan uppnås.
Deluppgifter
| Deluppgift | Poäng | Begränsningar: $n$ | Begränsningar: $m$ | Ytterligare begränsningar | Nödvändiga deluppgifter |
|---|---|---|---|---|---|
| 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$; alla hinder har höjden $1$ | |||
| 6 | 18 | Exempel, 1–5 |
Exempel
Indata 1
2 3 2 6 1 2 2 3 1 1 2 6 2 2
Utdata 1
4
Indata 2
1 3 1 5 2 2 2 1 1 9 2 1
Utdata 2
9
Förklaring
En av de optimala strategierna för att leverera beställningarna i det första exemplet visas i de nio bilderna nedan. Att utföra den andra beställningen ökar inte vinsten.
I det andra exemplet räcker det att klona roboten en gång för att leverera den första beställningen och använda den resulterande robotkonstruktionen för att leverera den andra beställningen. Att skapa ytterligare kloner för att leverera den tredje beställningen är inte ekonomiskt lönsamt.