Problem D
Frågetävling

I frågetävlingen ProgrammeringsQuiz finns det totalt $N$ frågor, fördelade över $M$ olika kategorier (t.ex. algoritmteori, kompilatorkonstruktion eller Sven-kunskap).

Frågorna är värda olika mycket poäng. Dessutom får du en bonus $B$ när du löser samtliga problem i en viss kategori. Simone har varit med i Programmeringsolympiaden sen åttonde klass, så hon kommer kunna svara rätt på alla frågor.

Tyvärr går tävlingen på tid. Trots att hon aldrig svarar fel kommer hon bara hinna svara på $K$ av frågorna. Vilken poäng kan Simone maximalt uppnå?

Input

Den första raden innehåller de fyra heltalen $1 \le N \le 1000$, $1 \le M \le N$, $1 \le K \le N$, $1 \le B \le 100\, 000$. De följande $N$ raderna innehåller två tal var: poängen för frågan (ett heltal mellan 1 och $1\, 000$) och vilken kategori den ingår i (mellan 1 och $M$). Det är garanterat att alla kategorier kommer att innehålla minst en fråga.

Output

Du ska skriva ut en enda rad med den maximala poängen du kan uppnå.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I det första exemplet svarar vi på båda frågorna i kategori 1 ($300 + 400 = 700$ poäng) och den enda frågan i kategori 2 ($200$ poäng). Eftersom dessa var de enda frågorna i de två kategorierna får vi även två stycken kategoribonusar, vilket ger totalt $200 + 700 + 2 \cdot 1000 = 2900$ poäng.

5 3 3 1000
300 1
400 1
200 2
200 3
300 3

2900

5 3 3 1
300 1
400 1
200 2
300 3
200 3

1001