990 - Diving for Gold

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

  • 金幣所在 $n$ 個不同的位置,以 $\{(d_1,v_1), (d_2,v_2), \cdots{},(d_n,v_n)\}$ 表示這 $n$ 個位置的 (深度, 金幣的數量),$n$ 最大為 30。
  • 氧氧桶最多可使用 $t$ 秒,$t$ 最多 1000 秒。
  • 每一次潛下水面,他可帶回所有沉在該位置的金幣。
  • 下沉所需的時間 ${td}_i$$w\times{d_i}$$w$ 為一常數。
  • 浮起所需的時間 ${ta}_i$$2w\times{d_i}$$w$ 為一常數。
  • 輸入的所有數值皆為整數。

Input

輸入有多組測試資料,每組資料的第一列有兩個整數分別表示 $t,w$,第二列有一個整數為 $n$,接下來的 $n$ 列,每列有兩個整數分別表示金幣所在的深度 $d_i$ 及數量 $v_i$

每組測試資料間有一空行隔開。

Output

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

請在每組輸出資料間以一列空行隔開。

Sample Input

210 4
3
10 5
10 1
7 2

Sample Output

7
2
10 5
7 2