13040번 - Important Test 다국어

Nick is going to take an important test soon, so he has decided to prepare. Test has n possible variants, the i-th of them has m_i tasks numbered from 1 to m_i. For each task of each variant Nick has estimated the time t_ij minutes that it would take him to solve it and write down.

The tasks in the test must be solved in order they appear in the test, one after another. The test must be submitted until deadline of t minutes. Nick thinks he could secretly copy some solutions from his notes, but he doesn't want to risk much. So he would copy at most one solution. Copying of any solution would take t₀ minutes.

Now Nick would like to find out for each variant what is the maximal number of tasks he could write down if he gets this variant.

The first line of input contains three integers: n, t and t₀ (1 ≤ n ≤ 100, 1 ≤ t ≤ 10 000, 1 ≤ t₀ ≤ 100) — the number of variants, the length of the test, and the time needed to secretly copy the solution from the notes.

The following n lines describe variants. The first integer m_i (1 ≤ m_i ≤ 100) is the number of tasks in the i-th variant. It is followed by mi integers t_ij (1 ≤ t_ij ≤ 100) — time needed for tasks.

For each variant print one integer: the number of tasks Nick can write down if he gets this variant.