물 파이프

이스트오너(Eastowner) 시는 늘 물 부족에 시달려서 새 상수도 파이프를 놓기로 했다. 공사는 양쪽 끝에서 동시에 시작되었고, 마침내 두 구간이 거의 이어졌다. 첫 번째 구간은 점 $(x_1, y_1)$에서 끝나고, 두 번째 구간은 점 $(x_2, y_2)$에서 끝난다. 남은 파이프 조각은 길이가 제각각인 몇 개뿐이다. 이 지역 기술의 특성상 각 조각은 남북 방향 또는 동서 방향으로만 놓을 수 있고, 두 조각은 일직선으로 이어지거나 $90^\circ$로 꺾이도록만 연결할 수 있다(즉, $180^\circ$로 되꺾는 U자 연결은 허용되지 않는다).

사용할 수 있는 조각의 길이 $L_1, \dots, L_k$와 길이가 $L_i$인 조각의 개수 $C_i$가 주어질 때, 점 $(x_1, y_1)$과 점 $(x_2, y_2)$를 잇는 파이프를 만들거나 불가능함을 판정하여라. 필요한 조각의 최소 개수를 출력한다.

정수 $x_1\ y_1\ x_2\ y_2\ k$가 주어지고, 이어서 $2k$개의 정수 $L_1\ L_2\ \dots\ L_k\ C_1\ C_2\ \dots\ C_k$가 주어진다. 값들은 공백이나 줄바꿈으로 구분된다.

필요한 조각의 최소 개수를 정수 하나로 출력한다. 연결이 불가능하면 $-1$을 출력한다.

• $1 \le k \le 4$
• $1 \le x_i, y_i, L_i \le 1000$
• $1 \le C_i \le 10$