你將承擔為大型會議廳設計照明系統的任務。

經過大量的計算和草圖繪製，你已經找到了節能設計的要求，並可以正確照亮整個大廳。

根據你的設計，你需要$n$種不同功率的燈，不過因為某些奇怪的電流調節方法，所以全部的燈泡都需要輸入相同的電流。

因此，每種燈都有相應的電壓($V$)。(功率 = 電壓 * 電流)

你已經知道你所設計的每種燈所需要的數量($L$)和其單價($C$)。

另外，每種燈都會需要不同的電源供應器(費用為$K$)，使燈泡能發光。

公司很快就發現，通過替換原本的燈泡變成其他更高電壓的燈泡可以降低總系統成本。

(例如 把一個200V單價10元的燈泡 換成 300V單價5元的燈泡)

且對於一個電源供應器，如果沒有燈泡連結至此，那此電源供應器也無須購買。

當然，永遠不能用低於原燈泡電壓的燈泡來替換，不然大廳的某些部分可能不會亮。

公司更在意省錢勝過節能。請找到設計系統所需的最低成本。

$\forall\;T\leq5\;\;n\leq5000\;\;V_i,\;K_i,\;C_i,\;L_i\leq10000$，且所有數皆為正整數

Subtask:

$(10 + 10)\%\;\;n\leq 500$

$(40 + 40)\%$ 無特別限制