Marching Course

Example

Input

3 3 4 1 2 1 1 2 3 2 4 3 1 1 1

Output

6

inputFormat

Input

3 3 4 1 2 1 1 2 3 2 4 3 1 1 1

outputFormat

Output

6

样例

3 3 4
1 2 1 1
2 3 2 4
3 1 1 1

6