IOICamp 是一個由臺大資工學生所舉辦的程式解題競賽集訓營，而小風是一位充滿著熱忱的營隊工作人員，他知道接下來會收到來自營隊總召波路特石的 $N$ 項任務，第 $i$ 項任務包括：

• 開始日期 $s_i$，代表這項任務在第 $s_i$ 天後便可以被執行。
• 截止日期 $e_i$，代表這項任務在第 $e_i+1$ 天後便不能再執行（也就是說，小風只能在第 $s_i\sim e_i$ 天執行第 $i$ 項任務）。
• $x_i$ 單位的工作，每一單位的工作都需要花費小風一天的時間完成。

由於小風是時間控管大師，他每一天可以隨意選擇任意一項任務的其中一單位工作執行（當然，要在該項任務的可執行時間內），不過這一天他就只能專心執行這一項任務，不可以更改。

為了鼓勵小風盡可能的完成多一點任務，波路特石額外又給他了一些獎勵。對於第 $i$ 個任務，波路特石設定了一個獎勵參數 $p_i$，代表如果小風完成了 $y_i$ 單位第 $i$ 項任務的工作，他可以獲得 $p_i\cdot y_i$ 塊錢，注意到即使小風沒有完成整項任務，他依然拿得到錢。

另外，由於總召的事情繁瑣，波路特石能定好任務細節的時間有限，已知他已經在心中挑選了至多隨意 $30$ 天來處理小風的任務，因此，開始日期的種類至多只有 $30$ 種。

請幫助小風找出在最佳的執行任務時間分配下，他最多可以拿到多少錢。