小智的學校在天空之城，他每天開直升機上學，現在他想要規劃一條路徑以便在從家裡到學校的路上可以抓到最多的寶貝，請你寫個程式幫助他。
我們將學校與他家之間所有的位置劃分成 N*N 的格子，每個格子以坐標(x,y)表示，其中 x 代表水平距離，y 代表高度，而小智家的坐標在(0,0)的位置，學校在(N-1,N1)的位置，由於他的父母不准他上學途中貪玩繞路，直升機被設定成每次只能向前或向上一格，也就是說，如果從(x,y)到(x+1,y)或(x,y+1)，當然，他也不可以超過x<N 且 y<N 範圍，否則會無法到達學校。

小智到學校的路途上一共有 N 隻寶貝，每隻寶貝可以補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說，對於寶貝 P(i), 0≦ i <N，要捕抓到 P(i)，小智必須經過下列座標之一：{(x,y)| S(i)≦x≦T(i) and y=i}，其中所有的S(i)與 T(i)都已經透過抓寶雷達得到資料了。

上圖是一個 N=5 的例子，藍色區塊顯示可以捕抓到寶貝的地方，請注意，每一個寶貝 都是在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的路徑，因為他每一步 都只有向右或向上，沿這一條路徑可以捕抓到四隻寶貝，是所有可能路徑中可以捕抓 到寶貝數最多的。