Alice's Game Challenge

Alice is playing a game that consists of ( n ) levels. In this game, you control a hero having two attributes: health and level. Initially, the hero starts with a health of ( m ) and level 1. At each level ( i ), the boss deals damage to the hero according to the hero's current level. Specifically, if the hero's level is ( j ), the boss causes ( b_{i,j} ) damage. After defeating the boss in level ( i ) (i.e. after the hero's health is reduced by the damage), you are given an experience book. You must choose one of the following two options:

1. Recover Health: Increase the hero's current health by ( a_i ). The hero's level remains unchanged.
2. Change Level: Change the hero's level to any integer between 1 and ( \text{current level} + 1 ) (inclusive). The hero's health remains unchanged.

At every moment throughout the game, the hero's health must remain greater than 0. For each ( k ) from 1 to ( n ), consider an independent playthrough where you go through exactly ( k ) levels (resetting the hero to the initial state for each query). Determine the maximum level the hero can achieve after clearing level ( k ) (after possibly using the ( k^{th} ) level's experience book). If it is impossible to clear level ( k ), the answer for that query is 0.

Input Constraints and Details:

• The game consists of ( n ) levels and the hero starts with health ( m ) and level 1.
• For each level ( i ):
  • The experience book can either add health ( a_i ) or change the hero's level.
  • The boss at level ( i ) deals damage ( b_{i,j} ) if the hero's current level is ( j ). Note that for level ( i ), ( j ) is defined for ( 1 \le j \le i ) (i.e. there are exactly ( i ) damage values for level ( i )).

Example:

For ( n = 3 ), ( m = 2 ), ( a = [2, 1, 1] ), and damage values:

• Level 1: ( b_{1,1} = 1 )
• Level 2: ( b_{2,1} = 2, \quad b_{2,2} = 3 )
• Level 3: ( b_{3,1} = 3, \quad b_{3,2} = 3, \quad b_{3,3} = 3 )

Playthrough analysis:

• For ( k = 1 ):

  • Level 1: Health goes from 2 to ( 2 - 1 = 1 ) after damage. Then, choosing to change the level (upgrade) and setting level to 2 yields a result of 2. Hence, the answer is 2.

• For ( k = 2 ):

  • Level 1: Health goes from 2 to 1 after damage. Then, choosing to recover health, the health becomes ( 1 + 2 = 3 ) with level still 1.
  • Level 2: With level 1, health goes from 3 to ( 3 - 2 = 1 ) after damage. Then, choosing to upgrade (change level) to 2 gives a result of 2. Hence, the answer is 2.

• For ( k = 3 ):

  • Regardless of the choices, it is impossible to clear level 3 while keeping the health above 0. Hence, the answer is 0.

Your task is to output ( n ) integers for queries ( k = 1 ) to ( n ), where the ( k^{th} ) integer is the maximum level achievable after level ( k ) or 0 if clearing level ( k ) is impossible.

inputFormat

The first line contains two integers ( n ) and ( m ), representing the number of levels and the initial health of the hero respectively.\n\nThe second line contains ( n ) integers: ( a_1, a_2, \dots, a_n ), where ( a_i ) represents the health recovery provided by the experience book at level ( i ).\n\nThis is followed by ( n ) lines. The ( i^{th} ) of these lines contains ( i ) integers: ( b_{i,1}, b_{i,2}, \dots, b_{i,i} ), where ( b_{i,j} ) is the damage dealt by the boss at level ( i ) if your hero's level is ( j ).

outputFormat

Output ( n ) space-separated integers. The ( k^{th} ) integer should be the maximum level the hero can achieve after clearing level ( k ) (after using the ( k^{th} ) experience book), or 0 if it is impossible to clear level ( k ).

sample

3 2
2 1 1
1
2 3
3 3 3

2 2 0