找不出狀態轉移方程
描述
一大堆期末考試來襲，草灘小王子被迫去上自習了。
除了自習，草灘小王子還想到了n件可以做的事，n件事可以選一些去做，
這些事會花費一定的時間並且必須一次完成不停止（本題中時間的最小單位為1秒）
並且可以提高（降低）草灘小王子自習的效率（神奇的是效率的提升是累加的），
草灘小王子一開始的效率只有1。
草灘小王子可以在任意時刻開始自習任意時間（效率不會因此降低），假設當前的效率為 ki ，
這段時間 ti內獲得的收獲 si=ti×ki 。
現在草灘小王子共有t秒的時間，該如何分配時間獲得最大的自習收獲呢。
輸入
第一行是一個整數T(T<=10)，代表測試數據的組數。 對於每組測試數據： 第一行含兩個個整數 t(0≤t≤1000),n(1≤n≤10000) 接下來n行，第行包括2個整數a,b(0≤a≤100,0≤b≤30)。 a代表第i件事所花的時間,b代表第i件事所提升的效率
輸出
對於每組測試數據，輸出一行，表示草灘小王子能夠獲得的最大收獲
輸入
1
20 3
10 5
6 2
5 4
輸出
75
hint
小王子花了5秒鐘做完第3件事，然後花15秒鐘去自習
