## LCC '21 Contest 1 J5 - Penelope's Pumpkins

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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

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

#### Input Specification

The first line of input will contain four space-separated integers, , , , and , 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 lines will contain two space-separated integers, and the cost and type of the -th pumpkin.

#### Output Specification

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

#### 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 , , , , , , , for a cost of .

#### 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.