Input
4 2 1 2 5 4 3 1 2 3 2 4 5 3
Output
5
Input
4 3 1 2 3 5 2 3 4 2 3 4 5 3 1 3 10 10
Output
-1