사파리

사파리는 야생동물을 보기 위해 자연으로 떠나는 여행이다. 참가자는 보통 사륜구동 차량, 줄여서 4WD 차량을 타고 넓은 초원을 달린다. 당신이 4WD 차량 $C$를 타고 사파리에 나섰다고 상상하라.

동물은 초원의 특정 장소에 나타난다. 이 장소를 평면 위의 점으로 본다. 동물은 $n$마리이며 1번부터 $n$번까지 번호가 붙어 있고, 동물 $i$는 점 $p_i$에 나타난다. 각 동물은 자기만의 시간 구간에만 나타난다. 구체적으로 동물 $i$는 $[a_i, b_i]$ 동안 나타난다. 차량 $C$가 $[v, w]$ 동안 $p_i$에 머물면, $[v, w] \cap [a_i, b_i]$ 동안 동물 $i$를 관찰할 수 있다. $[\alpha, \beta]$ 동안 동물을 관찰했다면 관찰 시간은 $|\beta - \alpha|$이다.

차량 $C$는 시각 0에 출발점 $s = (0, 0)$에서 출발하며 속력은 1이다. 따라서 거리 $d$를 이동하는 데 시간 $d$가 걸린다. 거리는 $L^1$ 거리로 잰다. 점 $p_1 = (x_1, y_1)$과 $p_2 = (x_2, y_2)$ 사이의 거리 $d(p_1, p_2)$는 $|x_1 - x_2| + |y_1 - y_2|$이다. $p_1$에서 $p_2$로 이동하는 데는 항상 $d(p_1, p_2)$만큼의 시간이 걸린다. 차량은 필요한 만큼 한 지점에 머물 수 있다.

사파리는 마지막으로 동물을 관찰한 지점에서 끝난다. 동물을 관찰할 수 있는 총 시간의 최댓값을 구하라.

첫 줄에 동물의 수 $n$ ($1 \le n \le 5000$)이 주어진다. 동물은 1번부터 $n$번까지 번호가 붙어 있다.

다음 $n$개 줄에는 동물 $i$가 나타나는 점 $p_i$의 좌표 $x_i$와 $y_i$가 정수로 주어진다 ($0 \le x_i, y_i \le 10^6$). 차량 $C$는 시각 0에 $(0, 0)$에 있다. 주어진 점들은 $(0, 0)$을 포함하여 모두 서로 다르다.

마지막 $n$개 줄에는 동물 $i$가 $p_i$에 나타나는 구간 $[v_i, w_i]$가 정수로 주어진다 ($0 \le v_i < w_i \le 10^9$).

동물을 관찰할 수 있는 총 시간의 최댓값을 한 줄로 출력하라.