CSES - KILO 2017 1/5 - Queue
  • Time limit: 1.50 s
  • Memory limit: 512 MB

n people from m different groups are waiting in a long queue outside of the airport. There are two buses, each with capacity of k people. Your task is to assign each person to a bus such that everyone from the same group is assigned to the same bus.

Each second a person who is the first of the queue enters the bus they are assigned to. A bus can leave the airport once everyone assigned to the bus has entered the bus. It takes one second from a person to enter a bus. Waiting time of a person is the time the bus with this person left the airport. You should minimize the sum of waiting times.

Input

The first line of input contains three integers, n, m and k, number of people, number of different groups and the capacity of one bus. The next lines contains n integers, a_1, a_2, \ldots, a_n, IDs of the groups of people in the order they are in the queue. The group IDs are in range 1..m, and it is possible that not all IDs are in use.

Output

If it is possible to assign everyone to buses print the minimum sum of waiting times. If it is not possible print -1.

Contraints

  • 1 \le n \le 10^5
  • 1 \le m \le 2000
  • 1 \le a_i \le m
  • 1 \le k \le 10^5

Examples

Input:

7 3 5
2 2 1 1 1 3 1

Output:

39

Assign people from group 2 to one bus and people from groups 1 and 3 to another. The waiting times are: 2 2 7 7 7 7 7

Input:

12 3 9
1 1 1 2 3 2 2 2 2 2 2 2

Output:

116

Input:

2 1 2
1 1

Output:

4

Input:

3 1 2
1 1 1

Output:

-1