990 - Diving for Gold

John是一位寶物獵人，他知道附近海域所有沉在海裡的金幣的位置及深度，及其金幣的數量，不過他只帶了一個氧氣桶過來，所需的氧氣量可能不夠讓他將所有的寶物全都打撈上來，請你幫忙計算他最多可帶回多少金幣，需符合下列限制條件：

• 金幣所在 n 個不同的位置，以{(d1, v1), (d2, v2), ..., (dn, vn)}表示這 n 個位置的(深度, 金幣的數量)，n 最大為30。
• 氧氧桶最多可使用 t 秒，t 最多1000秒。
• 每一次潛下水面，他可帶回所有沉在該位置的金幣。
• 下沉所需的時間為 w * di，w 為一常數，di 表示深度。
• 浮起所需的時間為 2w * di，w為一常數，di 表示深度。
• 輸入的所有數值皆為整數。

Input

輸入有多組測試資料，每組資料的第一列有兩個整數分別表示 t, w，第二列有一個整數為 n，接下來的 n 列，每列有兩個整數分別表示金幣所在的深度di及數量vi。
每組測試資料間有一空行隔開。

Output

請在每組測試資料的第一列輸出John可找到的所有金幣的數量，第二列輸出共需潛水幾次，之後的每一列輸出每次潛水的深度及帶回的金幣數量，其輸出順序需與輸入資料的金幣出現順序相同。
請在每組輸出資料間以一列空行隔開。

Sample input

210 4
3
10 5
10 1
7 2

Sample output

7
2
10 5
7 2

---

原文出處