30703번 - 온도 맞추기

문제

학교 실험실에 비커가 총 $N$개가 있고, 각 비커에는 1ドル$번부터 $N$번까지 번호가 붙어있다. $i$ 번 비커의 초기 온도는 섭씨 $A_i$도이다. $(1\leq i\leq N)$

기현이는 화학 실험을 위해 실험실에 있는 모든 비커의 온도를 각각 정해진 값에 맞추어야 한다. 구체적으로, $i$ 번 비커의 온도를 목표 온도인 섭씨 $B_i$도로 맞춰야 한다. 비커의 온도를 일일이 맞추기 귀찮았던 기현이는 편하게 온도를 조절할 수 있는 온도 조절 장치를 개발하였다!

온도 조절 장치는 버튼 하나로만 되어 있으며, 버튼을 한 번 누를 경우 아래와 같이 동작한다.

• 모든 $i$ $(1\leq i\leq N)$ 에 대해, $i$ 번 비커의 온도를 $X_i$도 올리거나 내린다. 비커마다 온도를 올릴지 내릴지를 기현이가 선택할 수 있으나, 온도를 그대로 유지하는 것은 불가능하다. $X_i$는 비커마다 사전에 정해진 온도 변화 수치이며, 이 값은 변하지 않는다.

온도 조절 장치가 한 번 동작하는 데는 시간이 걸리므로, 기현이는 온도 조절 장치의 버튼을 최소 횟수로 눌러서 모든 비커의 온도를 목표 온도로 맞추고 싶다.

비커의 개수와 각 비커의 초기 온도, 목표 온도, 온도 변화 수치가 주어졌을 때, 기현이가 비커들의 온도를 모두 맞추려면 버튼을 최소 몇 번 눌러야 하는지 구하여라.

온도 조절 장치만으로 모든 비커의 온도를 원하는 값에 맞추는 것이 불가능할 수도 있으므로, 이런 경우 역시 구별하여야 한다.

입력

첫 번째 줄에 비커의 개수 $N$이 주어진다. (1ドル\leq N\leq 100,000円$)

두 번째 줄에는 각 비커의 초기 온도를 나타내는 $N$개의 정수 $A_1, A_2, \cdots , A_N$이 공백으로 구분되어 주어진다. (0ドル\leq A_i\leq 10^9$)

세 번째 줄에는 각 비커의 목표 온도를 나타내는 $N$개의 정수 $B_1, B_2, \cdots , B_N$이 공백으로 구분되어 주어진다. (0ドル\leq B_i\leq 10^9$)

네 번째 줄에는 각 비커의 온도 변화 수치를 나타내는 $N$개의 정수 $X_1,X_2,\cdots ,X_N$이 공백으로 구분되어 주어진다. (1ドル\leq X_i\leq 10^9$)

출력

첫 번째 줄에 모든 비커의 온도를 목표 온도로 맞추기 위해 버튼을 누르는 최소 횟수를 출력한다.

만일 온도 조절 장치만으로 온도를 맞추는 것이 불가능하다면 -1을 대신 출력한다.

제한

힌트