Imagine the game as a ~6 \times M~ matrix, and the players as ~1 \times I~ blocks. We will fill up the matrix with players (blocks), without overlap. If a player covers the field ~(X, Y)~ in the matrix, it means they are playing position ~X~ in the ~Y^\text{th}~ minute of the game.

We fill out the matrix (game) by sorting the players by quality and iterating sequentially from the most quality player to the least quality player, and fill out the matrix row by row. If it so happens that a player's block doesn't fit entirely in the current row of the matrix, we break that block into two parts and continue with that player (block) in the following row.

This way, we made sure that we have the maximal possible sum of quality by the minute, since we used each player, starting from the most quality one, until their endurance limit (or less, in the case of the last player that might not fit entirely into the matrix).

We don't have to worry that a player will play multiple positions in the same minute, because its endurance is at most ~M~, and if they break from one row to another, they will never cover the same column (same minute of the game) in both rows (both positions), because the matrix width is ~M~.

As for the output, we will store the substitute when we're moving on to a new player (new block) in the corresponding minute and position, keeping track of the previous player (block), in order to know which player is leaving the game. If it's a player from the start of the row, we don't output the substitute, but place that player with the initial six players. We will output the substitutes chronologically in the end.

We need to be careful when outputting the substitutes. If a player is of endurance ~M~ and breaks into two parts, from row ~X~ to row ~X+1~, we will output them leaving the game in row ~X+1~, and their entrance in row ~X~ for the same minute. Substitutes where the player enters and leaves the game in the same minute are not allowed. We will solve this problem by checking if we are dealing with a player of endurance ~M~, and if they don't start in the first column, then we will place them in the matrix broken into two parts, but still keep track of the previous player, and declare them as the one leaving the game when the next player is entering.

The implementation details are not complex, and are left as an exercise to the reader.