Background

Special for beginners, ^_^

Description

Format

Input

Output

注意输出时：每行输出一个结果，行与行之间不要空行....

Samples

4 5 5
10000
2 1 1 1 2
3 1 1 1 3
4 1 2 1 4
1 2 3 4 1 5
1 2 1
01
31 1 2 1 1
3 5 5
10100
3 1 1 1 2
1 1 3 1 4
3 2 4 2 1 5
1 3 3
100
1 1 1 1 2
0 0 0

Case 1: 7
Case 2: 31
Case 3: 6
Case 4: -1

Limitation

(刘汝佳与唐文斌合著此题)