996 . 假廣告
TopCoder
Tags
Description
小明很喜歡玩手機遊戲，不過，最近他發現有些遊戲居然會做跟遊戲內容無關的廣告來吸引人下載，被欺騙的小明很生氣，於是他決定把這些假廣告的內容出成程式題目！
小明看到的其中一個廣告如上圖所示，是一個算數爬塔遊戲。遊戲中由左至右一共有 $N$ 座塔，第 $i$ 座塔上會有 $k_i$ 個敵人和 $s_i$ 把寶劍，每位敵人都擁有自己的戰力 $a_{i, j}$。玩家一開始會有戰力 $X$，並且從最左邊的塔出發。遊戲進行時，玩家可以挑選塔上任何一位尚未選過的敵人戰鬥，並且如果他的戰力不小於敵方戰力，他便能打倒對方，使自己的戰力成長為加上對方戰力後的數值。反之，玩家會戰敗，遊戲也會結束。
除了選擇敵人戰鬥外，如果塔上有還沒拾取的寶劍的話，玩家也可以選擇拾取一把寶劍，並讓自己的戰力成長為當下戰力的兩倍。當玩家挑戰完塔上的所有敵人，便可依序前往下一座塔。請注意所有寶劍只能在前往下一座塔前被拾取，玩家不可前往前一座塔拾取該塔內尚未拾取的寶劍。
現在，請你幫忙計算一下，如果使用最佳策略遊玩的話，最多可以挑戰完幾座敵方的塔呢？
Input Format
輸入第一行包含兩個正整數 $N$ 和 $X$，代表塔的數量和玩家的初始戰力。
接下來包含 $N$ 行，第 $i$ 行首先會有一個正整數 $k_i$ 和一個非負整數 $s_i$，代表第 $i$ 座塔的敵人數量和寶劍數量。接著會有 $k_i$ 個正整數 $a_{i,1}, a_{i, 2}, \ldots, a_{i, k_i}$，代表每個敵人的戰力。
- $1 \leq N \leq 10 ^ 5$
- $1 \leq \sum_i (k_i + s_i) \leq 10 ^ 6$
- $k_i \geq 1, s_i \geq 0$
- $1 \leq a_{i, j}, X \leq 10 ^ 9$
Output Format
輸出一個非負整數，代表最多可以挑戰完成的塔數量。
Sample Input 1
1 22 3 0 21 75 38
Sample Output 1
1
Sample Input 2
3 10 2 0 5 12 3 1 48 25 99 2 0 300 500
Sample Output 2
3
Sample Input 3
3 10 2 0 5 12 3 1 48 25 99 2 0 300 1000
Sample Output 3
2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|