Map Labeling

Map labeling places extra information, usually a text label, next to the features of interest on a map. A map typically shows line features (roads, rivers), area features (countries, forests, lakes), and point features (villages, cities). This problem considers point features only.

The basic requirements are that labels do not overlap each other and that each label lies close to the feature it belongs to. Large labels or a dense set of features make both requirements impossible to meet at once, so here a label may sit far from its feature as long as the labels stay pairwise disjoint. Every feature is joined to its label by a polygonal line called a connector, and connectors must not intersect each other. Only two kinds of connector exist. A straight connector is a single vertical segment. A bended connector is three connected segments: vertical, horizontal, then vertical again. See Figure G.1.

There is a line $L$, taken as the x-axis, and $n$ points lie on it, one for each point feature. The coordinates of the $n$ points are distinct. A label is a rectangular area of height 1, so point $p_i$ at coordinate $a_i$ has an axis-parallel rectangular label $l_i$ of width $w_i$ and height 1. All labels have the same height. Let $U$ be the line parallel to $L$, above $L$, at vertical distance 1 from $L$. Each label rests with its lower side on $U$ and its body above $U$, as in Figure G.1. Labels must be pairwise disjoint, but two labels may touch along their boundaries.

Figure G.1 Rectangular labels of point features

Write the position of $l_i$ as the interval $[x_i, x_i + w_i]$ on $U$. A connector runs from its point to the lower side of its own label and stays inside the strip between $L$ and $U$. The connector of $p_i$ is straight exactly when $x_i \le a_i \le x_i + w_i$, because then the vertical segment from $(a_i, 0)$ to $(a_i, 1)$ reaches $l_i$. Otherwise the connector is bended.

Write a program that finds a placement of the labels minimizing the number of bended connectors. For the points and labels of Figure G.1, the placement in Figure G.2 attains the minimum.

Figure G.2 Optimal placement of labels

Your program reads from standard input. The first line has an integer $n$ ($1 \le n \le 10000$), the number of points on $L$. Each of the next $n$ lines has the coordinate $a_i$ of the $i$-th point, an integer with $0 \le a_i \le 10^8$. The coordinates are distinct, so $a_i \ne a_j$ when $i \ne j$. Each of the following $n$ lines has the width $w_i$ of the label of the $i$-th point, an integer with $1 \le w_i \le 10^5$. All labels have height 1.

Your program writes to standard output. Print one line holding the minimum number of bended connectors over all valid placements.