10198 - Counting

Gustavo小朋友剛學會算術，並且正在學習寫數字，他已經學會寫1, 2, 3, 4，不過他並不知道4與1是不同的數字，以為4是1的另一種寫法。另外，他還發明了一個小遊戲，寫出一個數字(僅含他已知的四個數字)將每一位數相加得到另一個數字，例如：

132 = 1 + 3 + 2 = 6 

112314 = 1 + 1 + 2 + 3 + 1 + 1 = 9 (因為他以為 4 = 1) 

在做了很多計算之後，他很好奇有幾個不同的數字其每一位數和同為n，例如當n=2，他發現有5組數字：11, 14, 41, 44, 2(他會加法，但還不會寫5)，不過他不清楚當n大於2時共有幾組，所以他請你幫他。

The Input

讀取輸入直到遇見EOF為止會有任意多組數值，每一個數值的範圍為 1 <= n <= 1000。

The Output

你的輸出必須計算共有多少組數值，其每一位數之和為n。

Sample Input

2
3

Sample Output

5
13

原文出處

10130 - SuperSale

在SuperHiperMarket賣場有促銷活動，每種商品每人都能用超低的價格各買一件，例如一台超低價電視、一根超低價蘿蔔，我們全家總動員要去大採購，不過每人能提的重量有限。我們已經準備好了欲採購物品的清單，記錄著每件物品的價格與重量，我們也知道自已最多能提多少重量，請問我們這次採購能買到物品的最高總值為何？

Input Specification

1. 第一列為整數T，表示有多少組測試資料。

2. 每組測試資料分為兩部份，第一部份一開始有一整數N，表示接下來共有N件物品，而接下來的每一列為這N件物品的價格(P, 1<=P<=100)與重量(W, 1<=W<=30)。

3. 緊接著第二部份為一整數G，表示群組內的人數，接下來有G列表示每個人最大能提的總重量(MW, 1<=MW<=30)。

Output Specification

請依每組測試資料輸出一個整數：全家人能買到物品的最高總值。

Sample Input

2

3

72 17

44 23

31 24

1

26

6

64 26

85 22

52 4

99 18

39 13

54 9

4

23

20

20

26

Output for the Sample Input

72

514

---

原文出處