原題： In the hourglass to the right a path is marked. A path always starts at the first row and ends at the last row. Each cell in the path (except the first) should be directly below to the left or right of the cell in the path in the PRevious row. The value of a path is the sum of the values in each cell in the path. A path is described with an integer representing the starting point in the first row (the leftmost cell being 0) followed by a direction string containing the letters ‘L’ and ‘R’, telling whether to go to the left or right. For instance, the path to the picture is described as ‘2 RRRLLRRRLR’. Given the values of each cell in an hourglass as well as an integer S, calculate the number of distinct paths with value S. If at least one path exist, you should also print the path with the lowest starting point. If several such paths exist, select the one which has the lexicographically smallest direction string. Input The input contains several cases. Each case starts with a line containing two integers N and S (2 ≤ N ≤ 20, 0 ≤ S < 500), the number of cells in the first row of the hourglass and the desired sum. Next follows 2N ? 1 lines describing each row in the hourglass. Each line contains a space separated list of integers between 0 and 9 inclusive. The first of these lines will contain N integers, then N ? 1, …, 2, 1, 2, …, N ? 1, N. The input will terminate with N = S = 0. This case should not be processed. There will be less than 30 cases in the input. Output For each case, first output the number of distinct paths. If at least one path exist, output on the next line the description of the path mentioned above. If no path exist, output a blank line instead. Sample Input 6 41 6 7 2 3 6 8 1 8 0 7 1 2 6 5 7 3 1 0 7 6 8 8 8 6 5 3 9 5 9 5 6 4 4 1 3 2 6 9 4 3 8 2 7 3 1 2 3 5 5 26 2 8 7 2 5 3 6 0 2 1 3 4 2 5 3 7 2 2 9 3 1 0 4 4 4 8 7 2 3 0 0 Sample Output 1 2 RRRLLRRRLR 0

5 2 RLLRRRLR

中文： 來自（lucky 貓） 在左邊像沙漏的圖中有一條路徑被標示出來。在沙漏中的路徑總是從最上方開始到最下方結束。當由某列中的某個格子往下列走時只能往左或往右一格。而路徑的值就是經過格子的值的總和。

一條路徑以一個數字以及一連串的動作組成。數字代表此路徑從最上方一列的哪一個格子開始走起（最左方的格子編號為 0）。動作為 R 或 L 其中之一，代表該往右下或左下方走。以左圖中的路徑為例：該路徑為 2 RRRLLRRRLR

給你沙漏中每個格子的值，以及一個數 S，請你算出有多少條路徑的值為S。如果不只一條這樣的路徑存在，輸出最上方列起始位置最小的那條。如果還是不只一條存在，則輸出字典順序最小的那條。

Input

每組測試資料的第一列有2個整數N,S（2 <=N <= 20, 0 <= S < 500）。N代表沙漏中最上方列格子的數目，S代表要求路徑的值。接下來的 2N-1 列描述此沙漏中每一列的情形。每一列中的數字均介於 0 到 9 之間，且以一空白字元相隔。沙漏中各列的格子數分別為N, N-1, …, 2, 1, 2, …, N-1, N.

當N=S=0時代表輸入結束，測試資料的數目不會超過30。請參考Sample Input。

Output

對每組測試資料請輸出2列。 第一列為路徑的數目，第二列為所要求路徑的表示法。如果所要求路徑不存在，第二列請輸出空白列。請參考Sample Output。

從上往下算（沒算路徑）

思路：

類似數塔問題，由于要求路徑數，需要考慮每個數取得以后是否能夠滿足和為固定的s，所以需要記錄s的值，又類似背包的問題。以倒三角威力，對于一個格，可以由左上的格子轉移，也可以又右上的格子轉移，所以狀態轉移方程為（從上往下算hg[i][j]為格子中的數）

dp[s][i][j]+=dp[s-hg[i][j]][i-1][j]+dp[s-hg[i][j]][i-1][j+1] (倒放的三角形） dp[s][i][j]+=dp[s-hg[i][j]][i-1][j]+dp[s-hg[i][j]][i-1][j-1] (正放的三角形）

但是此題不能從上往下算，因為打印路徑的緣故，所以需要從底部往頂部推導。