最近 Zisk 工廠接到了 $N$ 項工作，已知第 $i$ 項工作必須在第 $i$ 天執行，只要當天能滿足讓視察人員滿意的條件，Zisk 工廠就能夠獲得 $w_i$ 的報酬。

而要不管是工作還是視察條件，都高度與當天在處理工作的人員階級有關。已知 Zisk 工廠共有 $N$ 位員工，員工的階級分佈在 $1\sim N$ 之間、互相不重複，而根據排班表，第 $i$ 天來上班的員工會是階級 $p_i$ 的人，為了方便我們簡稱其為員工 $i$。

Zisk 身為工廠的老闆，決定適當的指定工作給員工、並付與他們當初談好的臨時工作薪資 $c_i$ 來最大化獲益。具體來說，Zisk 要指定第 $i$ 天的工作，就得花費 $c_i$ 來指定給第 $i$ 天待在公司的員工。而第 $i$ 天能獲得報酬的條件則被一個區間 $[l_i, r_i]$ 所決定，代表只要當天執行工作的人員階級 $p$ 滿足 $l_i\leq p\leq r_i$ 就可以獲得 $w_i$ 的報酬。

由於 Zisk 工廠是一間黑心工廠，為了最大化獲利，Zisk 在第 $i$ 天要分發工作給員工 $i$ 的同時，會根據最佳策略來強迫他在接下來的幾天留守在公司內繼續執行工作。也就是說，所有 $N$ 項工作會被 Zisk 切成若干段區間，若一段區間包含了第 $u\sim v$ 天的工作，那麼這些工作都會被員工 $u$ 所執行，並在這期間的每一天都利用員工 $u$ 的階級 $p_u$ 進行報酬的判定。而因為 Zisk 很黑心，沒有事先講好臨時工作的定義，因此他還只是需要支付 $c_u$ 給該名員工就好。

此時，一段日期區間 $[u, v]$ 的報酬可以被定義為

$$
-c_u + \sum_{u\leq i\leq v,\ l_i\leq p_u\leq r_i} w_i
$$

不過，Zisk 工廠這麼黑心，裡面的員工當然沒有多有良心。當員工 $u$ 被指派到日期區間 $[u, v]$ 的工作時，他會試圖偷懶，因為員工們都知道 Zisk 忙著數錢只會在第 $v$ 天來檢查該日期區間的收益，因此他會試圖找到一個在第 $u$ 天到第 $v$ 天之間有來上班的員工 $j$，使得這名員工的階級比他低，也就是 $p_j\leq p_u$。

找到這名員工後，階級員工 $u$ 就會偷懶直到員工 $j$ 來上班，然後開始使用階級的不對等壓榨他工作到第 $v$ 天為止，在這個期間，員工 $j$ 將會沒辦法再次找到一個替死鬼幫他工作，因為員工 $u$ 會控制住他的行為；同時，當視察人員來進行給予報酬的判定時，員工 $u$ 會親自出面來進行報酬判定，因此在第 $j$ 到 $v$ 天之間，第 $i$ 天給予報酬的條件依然會是 $l_i \leq p_u\leq r_i$，不過因為第 $u$ 到 $j-1$ 天期間員工 $u$ 會偷懶，所以這幾天無法獲得任何報酬。當然，如果員工 $u$ 找不到任何一個階級比他低的員工，那他也只能認命乖乖把區間 $[u, v]$ 的工作做完。另外關於臨時工作薪資的部份，員工 $u$ 會使用手段來調整自己的臨時工作薪資變成 $c_j$，這是為了騙過工廠內部的檢查系統所需要執行的必要步驟。

由於我們無法預測員工 $u$ 會瞄準哪一位員工當替死鬼，甚至有可能不偷懶，因此這時一段日期區間 $[u, v]$ 的報酬必須要想成最差的狀況，也就是

$$
\min_{u\leq j\leq v,\ p_j\leq p_u}\left\lbrace -c_j + \sum_{j\leq i\leq v,\ l_i\leq p_u\leq r_i} w_i\right\rbrace
$$

要注意到因為臨時工作薪資的替換，式子裡的 $c_u$ 被換成了 $c_j$。

身為 Zisk 的秘書，你能在不干涉 Zisk 工廠文化的情況下，幫 Zisk 找出將 $N$ 天的工作切割成若干段日期區間最佳切割方法，使得每一段區間的最差獲利總和最大嗎？