題目描述

妮可成功進入水底機器人國際總決賽，決賽要求機器人要用電池驅動。她正為這次的其中一個重要任務作規劃。

這個任務是這樣的：機器人要從一條筆直的水道的一端開始，水道的總長度為 L 厘米。沿水道上不同的位置 ( 距離起點為 d_i 厘米 ) 上有些不同重量沉在水底的物件，這些物件有不同得分值 p_i，妮可要做的就是把其中一些 ( 任意選擇 ) 物件拾起放在機器人的貨籃內，並把它們帶到終點。但整個運送過程受著以下實際條件的限制：

• 若能成功將物件運到終點，妮可的得分會是所有運到終點物件的分值總和
• 機器人在水底每前進 1 厘米，就需要使用 1 + n_t 單位的電力，其中 n_t 是機器人在這 1 厘米運行時所負載的物件的總數目
• 在開始時，機器人的電池共有 P 個單位的電力
• 若在未到達終點前電力耗盡，則任務失敗而得不到任何分數。若到達終點時電力剛好耗盡或有餘，則任務都算是成功，可以得到應有的分數
• 假設妮可的機器人的載貨籃是可以把所有的物件都裝下

現在比賽大會已公佈了每件物件的位置及其得分值 ( 所有這些數值均為正整數 )。妮可要做的就是估算一下她最多可以得到多少分？

輸入格式

輸入的第一行有三個正整數 L, P, N，分別代表水道的總長度，電池最初的電量以及物件的總數。( 100 <= L <= 1000000, L <= P <= 20000000, 1 <= N <= 30 )

隨後的 N 行上，每行有一對正數 d_i 及 p_i，代表第 i 件物件與起點的距離及其得分值，其中 0 < d_i < L 而 1 <= p_i <= 100

輸出格式

輸出資料應只含有一個整數，它代表兩個輸入整數的和。

Samples

100 110 4
1 100
96 7
95 5
98 4

12

提示

#非官方測試數據

原始資料

• Zero1 題號：a675
• Hydro 題號：Z0675
• Locale：zh_TW
• Display：open