Stamina Optimized Ice Cream Challenge

You are given a game with n levels. Level i costs \(s_i\) stamina per play and can be played at most \(m_i\) times. In order to play level \(i\) (for \(i \ge 2\)), you must have played level \(i-1\) at least once. Each play of level i involves an ice cream eating mini‐game described below.

For level \(i\), there are \(k_i\) ice creams arranged in a row. The j-th ice cream has a deliciousness value \(y_{i,j}\). Each play of the level requires you to eat all \(k_i\) ice creams in exactly \(k_i\) moves. The scoring is as follows: on the \(j\)-th move, if you eat the \(l\)-th ice cream, you earn \(j \times y_{i,l}\) points.

The twist is in the order in which you choose to eat the ice creams. You must eat the \(c_i\)-th ice cream on your first move. For every subsequent move, you may only eat an ice cream that is immediately adjacent to the contiguous block of already eaten ice creams. For example, if you start by eating the 2^nd ice cream, then on your second move you can only choose the 1^st or the 3^rd ice cream (if available).

Your task is to maximize the total score you can achieve by playing some levels subject to a total stamina limit \(t\). Note that if you decide to play a level \(i\) (for \(i \ge 2\)) you must have played level \(i-1\) at least once. For each level played, you may choose any number of plays within the allowed limit \(m_i\) (with at least 1 play if the level is unlocked) and each play of level \(i\) yields the same maximum score computed from the ice cream game described above. Formally, if the maximum obtainable score in one play of level \(i\) is \(B_i\), and you choose to play it \(x_i\) times (where \(1 \le x_i \le m_i\)), then you earn \(x_i \times B_i\) points and spend \(x_i \times s_i\) stamina. Levels that are not played will lock all subsequent levels.

You are to determine the maximum total score that can be achieved without exceeding the stamina limit \(t\). The optimal strategy involves deciding up to which level to play and how many times to play each unlocked level.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(t\) -- the number of levels and the total available stamina.

For each level \(i\) (from 1 to \(n\)), there are two lines of input:

• The first line contains four integers: \(s_i\), \(m_i\), \(k_i\), and \(c_i\), where \(s_i\) is the stamina cost per play, \(m_i\) is the maximum number of plays allowed, \(k_i\) is the number of ice creams, and \(c_i\) is the index of the ice cream that must be eaten first.
• The second line contains \(k_i\) integers: \(y_{i,1}, y_{i,2}, \dots, y_{i,k_i}\), representing the deliciousness values of the ice creams.

outputFormat

Output a single integer representing the maximum total score that can be achieved without exceeding the stamina limit \(t\).

sample

1 10
2 5 3 2
3 1 2

70