Islam prayer in congregation (jama'ah) is considered to have more social and spiritual benefit than praying by oneself. When praying in congregation, the people stand in straight parallel rows behind the chosen imam, facing Qibla (The Qibla is the direction that should be faced when a Muslim prays). Sometimes some of these rows are cut by poles (n poles divide the row into n+1 parts), and some of the rows do not contain poles (the whole row is just one part). Muslims prefer to stand in the rows which are free of poles, so they may leave one row empty and use the next one if it has fewer poles, but they can’t leave two consecutive rows empty.

A mosque is divided into n rows each row may contains one or more poles. Each row free of poles can have m Muslims and every additional pole decreases this number by 2, so if the row contains 2 poles, number of Muslims who can stand in this row is m - 4.

In this problem you are required to arrange the Muslims in rows where number of poles cutting these rows is minimized.

Input

Input contains multiple test cases. Each test case will start with the number of n (0 < n <= 100), m (10 <= m <= 200), and t (0 < t <= 20,000), where n is number of rows, m is number of Muslims per row, and t is the total number of people in the mosque, followed by n lines each containing the number of poles in each row. It is guaranteed that the mosque always can fit all the Muslims. Input will be terminated by end of file.

Output

For each test case, print one line containing the minimum number of poles cutting the prayer rows.

Sample

Input:
8 10 26
1
2
0
2
1
1
1
2
8 10 27
1
2
0
2
1
1
1
2
8 10 27
1
2
1
2
2
1
1
1

Output:
2
3
5