Elevator

Time Limit: 8 sec / Memory Limit: 64 MB

Example

Input

3 3 2 1 1 2 1 1 3 1 1 1

Output

8

inputFormat

Input

3 3 2 1 1 2 1 1 3 1 1 1

outputFormat

Output

8

样例

3 3 2
1 1
2 1 1
3 1 1 1

8