John 是一位寶物獵人，他知道附近海域所有沉在海裡的金幣的位置及深度，及其金幣的數量，不過他只帶了一個氧氣桶過來，所需的氧氣量可能不夠讓他將所有的寶物全都打撈上來，請你幫忙計算他最多可帶回多少金幣，需符合下列限制條件：
- 金幣所在 n 個不同的位置，以 {(d1,v1),(d2,v2),⋯,(dn,vn)} 表示這 n 個位置的 (深度, 金幣的數量)，n 最大為 30。
- 氧氧桶最多可使用 t 秒，t 最多 1000 秒。
- 每一次潛下水面，他可帶回所有沉在該位置的金幣。
- 下沉所需的時間 tdi 為 w×di，w 為一常數。
- 浮起所需的時間 tai 為 2w×di，w 為一常數。
- 輸入的所有數值皆為整數。
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