小智的學校在天空之城，父母親每天開直升機送他上下學，上學途中小智可以一邊抓寶。請寫個程式幫助小智的父母親規劃一條路徑以便在從家裡到學校的路上，小智可以抓到最多的寶貝。

學校與小智家之間所有的位置均等劃分成 $N \times N$ 的格子（如下所示），每個格子以座標 $(x, y)$ 表示，其中 $x$ 代表水平距離，$y$ 代表高度，若小智家的座標設為原點 $(0, 0)$，學校的座標則為 $(N-1, N-1)$。 直升機飛行的路線被設定成每次只能向右或向上推進一格，也就是說，若直升機在 $(x, y)$ 上，下一步只能飛達 $(x+1, y)$ 或 $(x, y+1)$，當然，直升機也不可以飛超過 $0 \le x<N$ 及 $0 \le y < N$ 的範圍。

小智上學的路途上一共有 $N$ 隻寶貝，每隻寶貝可以被補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說，對於寶貝 $P(i), 0 \le i < N$，要捕抓到 $P(i)$，小智必須經過下列座標之一：$\{(x, y)| S(i)\leq x\leq T(i), y=i\}$，其中 $0 \le S(i), T(i) <N$。

上圖是一個N=5 的例子，藍色區塊顯示可以捕抓到寶貝的座標位置，例如寶貝0 (P(0))的捕獲區域為 S(0)≦x≦T(0) (而S(0)=1, T(0)=2)，且y = 0。每一個寶貝可捕獲區域都一定在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的飛行路徑，因為每一步都只有向右或向上，沿這一條路徑共可以捕抓到四隻寶貝，即P(0), P(1), P(2), P(4)，也是所有可能路徑中可以捕抓到寶貝數最多的。