지도 라벨 배치

지도 라벨 배치는 지도에 있는 대상 옆에 보통 글자 라벨 형태로 정보를 덧붙이는 작업이다. 지도에 그려지는 대상은 선 대상(도로, 강 등), 면 대상(국가, 숲, 호수 등), 점 대상(마을, 도시 등)이 있다. 이 문제에서는 점 대상만 다룬다.

라벨 배치의 기본 조건은 라벨끼리 겹치지 않는 것과 라벨이 자신의 대상 가까이 놓이는 것이다. 라벨이 너무 크거나 대상이 빽빽하면 두 조건을 동시에 만족시키지 못한다. 그래서 이 문제에서는 라벨끼리 서로 겹치지만 않는다면 라벨이 자신의 대상에서 멀리 떨어져도 된다. 대신 각 대상은 연결선이라고 부르는 꺾은선으로 자신의 라벨과 이어야 하고, 연결선끼리 교차해서는 안 된다. 연결선은 두 종류뿐이다. 수직 선분 하나로 이루어진 연결선을 직선 연결선, 수직 선분, 수평 선분, 수직 선분이 차례로 이어진 연결선을 꺾인 연결선이라고 한다. 그림 G.1을 참고하라.

x축으로 삼는 직선 $L$ 위에 점 대상에 해당하는 점 $n$개가 있고, 이 $n$개 점의 좌표는 모두 다르다. 라벨은 높이가 1인 직사각형 영역이다. 즉 좌표가 $a_i$인 점 $p_i$에는 너비가 $w_i$이고 높이가 1이며 축에 평행한 직사각형 라벨 $l_i$가 대응한다. 모든 라벨의 높이는 같다. $L$과 평행하고 $L$보다 위에 있으며 $L$과의 수직 거리가 1인 직선 $U$를 생각하자. 각 라벨은 그림 G.1처럼 아래쪽 변이 $U$에 닿고 몸체가 $U$ 위에 오도록 놓는다. 라벨끼리는 서로 겹치면 안 되지만 경계가 맞닿는 것은 괜찮다.

그림 G.1 점 대상의 직사각형 라벨

$l_i$가 놓인 위치를 $U$ 위의 구간 $[x_i, x_i + w_i]$로 나타내자. 연결선은 자신의 점에서 출발해 자신의 라벨의 아래쪽 변에 닿으며, $L$과 $U$ 사이의 띠를 벗어나지 않는다. $x_i \le a_i \le x_i + w_i$이면 $(a_i, 0)$에서 $(a_i, 1)$로 가는 수직 선분이 $l_i$에 닿으므로 $p_i$의 연결선은 직선 연결선이 되고, 그렇지 않으면 꺾인 연결선이 된다.

꺾인 연결선의 개수를 최소로 만드는 라벨 배치를 찾는 프로그램을 작성하라. 그림 G.1의 점과 라벨이라면 그림 G.2의 배치가 최소를 이룬다.

그림 G.2 라벨의 최적 배치

프로그램은 표준 입력으로 읽는다. 첫 줄에 $L$ 위에 있는 점의 개수 $n$이 주어진다 ($1 \le n \le 10000$). 이어지는 $n$개 줄 중 $i$번째 줄에는 $i$번째 점의 좌표 $a_i$가 주어지며, $a_i$는 $0 \le a_i \le 10^8$인 정수이다. 점의 좌표는 모두 다르므로 $i \ne j$이면 $a_i \ne a_j$이다. 그 다음 $n$개 줄 중 $i$번째 줄에는 $i$번째 점에 대응하는 라벨의 너비 $w_i$가 주어지며, $w_i$는 $1 \le w_i \le 10^5$인 정수이다. 모든 라벨의 높이는 1이다.

프로그램은 표준 출력으로 쓴다. 올바른 모든 배치 중 꺾인 연결선 개수의 최솟값을 한 줄에 출력한다.