Penelope is going pumpkin picking for Halloween! She is visiting a pumpkin patch with ~N~ giant pumpkins. Each pumpkin is one of ~M~ types. Penelope would like to have ~K~ giant pumpkins for decorating her yard. Unfortunately, since the pumpkins are very large, she can only take home ~1~ giant pumpkin a day. In addition, in order to have a variety of pumpkins, after purchasing a pumpkin of type ~T_i~, Penelope does not want to purchase that same type for the next ~X~ days.

Each pumpkin has a cost of ~C~. Penelope would like know the minimum cost required to take home ~K~ giant pumpkins in ~K~ days.

Input Specification

The first line of input will contain four space-separated integers, ~N (1 \leq N \leq 10^5)~, ~M (1 \leq M \leq N)~, ~K (1 \leq K \leq N)~, and ~X (0 \leq X \leq K)~, the number of giant pumpkins in the patch, the number of types of pumpkins, the number of pumpkins Penelope would like to take home, and how many days Penelope would like between taking two pumpkins of the same type.

The next ~N~ lines will contain two space-separated integers, ~C_i (1 \leq C_i \leq 10^5)~ and ~T_i (1 \leq T_i \leq M)~ the cost and type of the ~i~-th pumpkin.

Output Specification

Output a single integer, the minimum cost required to take home ~K~ giant pumpkins, or -1 if Penelope cannot take home ~K~ pumpkins.

Subtasks

Subtask 1 [5%]

~X = 0~

Subtask 2 [5%]

~X = 1~

Subtask 3 [10%]

~N \leq 10~

Subtask 4 [80%]

No additional constraints.

Sample Input 1

10 5 7 3
1 1
1 3
4 3
2 4
10 2
100 1
1 1
62 4
90 3
100000 5

Sample Output 1

81

Explanation for Sample 1

Penelope can take the pumpkins in the order ~1~, ~2~, ~4~, ~5~, ~6~, ~3~, ~7~, for a cost of ~1 + 1 + 2 + 10 + 1 + 4 + 62 = 81~.

Sample Input 2

6 2 4 2
10 1
5 1
2 1
3 2
7 2
1000 2

Sample Output 2

-1

Explanation for Sample 2

Penelope cannot choose any order of pumpkins that meet her requirements.