Minimum Cost Flow

Examples

Input

4 5 2 0 1 2 1 0 2 1 2 1 2 1 1 1 3 1 3 2 3 2 1

Output

6

Input

Output

inputFormat

Input

4 5 2 0 1 2 1 0 2 1 2 1 2 1 1 1 3 1 3 2 3 2 1

outputFormat

Output

6

Input

Output

样例

4 5 2
0 1 2 1
0 2 1 2
1 2 1 1
1 3 1 3
2 3 2 1

6