Problem H
Walt Bellamy

Image from Wikimedia Commons; Public Domain

Walt Bellamy holds the record for the most NBA games played in a single season. You might be wondering, “But every team plays the same number of games each year, so how can one player hold the record for most games played?” In 1968–1969, Walt played in $88$ regular-season games, even though each team played only $82$ games. The reason is that Walt was traded in the middle of the year. He played $35$ games with his first team (NY Knicks), and $53$ games with his second team (Detroit Pistons), for a total of $88$ games.

The NBA wants to know if Walt Bellamy’s record can ever be beaten, but this seems very difficult to work out on paper, so you are being offered an obscene amount of money to write a computer program to answer this question. Given a list of the days on which each team plays, determine the maximum number of games that a single player could potentially play if they were able to be traded from one team to another (possibly multiple times) during the season.

Rules / Assumptions:

• One game per player per day: All basketball games take place at the same time of the day, so a basketball player can only play one game per day, and any trades that take place happen at the very end of the day. In other words, a player can play a game for a particular team and then be traded later that day.

• Trade deadline: No trades can happen after a specified day of the season. For example, if the trade deadline is $\textrm{day}~ 29$, then trades can happen on $\textrm{day}~ 29$ (and before), but no trades can happen on $\textrm{day~ }30$ or later. Note that days of the season are numbered $1, 2, 3, \ldots $. In the special case that the trade deadline is given as $\textrm{day}~ 0$, this means that no trades at all can happen during the season.

• Waiting period: A player must spend at least a specified number of days with a team after being traded to that team before they can be traded again. Remember that trades happen at the very end of a day, so if a player is traded on $\textrm{day}~ 6$ of the season, and the waiting period is $2~ \textrm{days}$, then they cannot be traded again until the very end of $\textrm{day}~ 8$ (i.e., they cannot play a game for a different team on $\textrm{day}~ 8$). Note the waiting period only applies after a player has been traded, so a player has no such obligation to remain on the team with which the player starts the season.

• No-limits trading: A player may be traded any number of times during the season, subject to the rules above.

Input

The first line of input contains five space-separated integers, $N~ S~ L~ W~ G$, where $N$ is the number of teams $(2 \leq N \leq 100)$, $S~ \textrm{is}$ the number of days in the season $(1 \leq S \leq 365)$, $L~ \textrm{is}$ the last trading day of the season $(0 \leq L \leq S)$, $W~ \textrm{is}$ the number of days a traded player must remain with their new team before they can be traded again $(1 \leq W \leq S)$, and $G~ \textrm{is}$ the number of games each team plays per season $(1 \leq G \leq S)$. This is followed by $N$ lines, one per team, each of which contains $G$ space-separated integers, $d_1, d_2, \ldots , d_ G$, where $d_ i$ is the day on which that team plays the $i^{\textrm{th}}$ game of its season. These $G$ values are ordered from lowest to highest, i.e., $1 \leq d_1 < d_2 < \ldots < d_ G \leq S$.

Note: This “game-day” schedule (which lists the days on which each team plays games) may not actually be feasible, i.e., there may not be a “full” schedule (one that also specifies which two teams play against each other in each game) that yields this game-day schedule. For example, the input may say that only one team has a game on a particular day, but of course that is impossible. For the purposes of solving the problem, you can ignore this deviation from reality.

Output

Output a single integer: the maximum number of games that a single player can play in the season.

3 6 2 2 4
1 2 3 4
1 2 5 6
3 4 5 6

6

3 10 0 1 4
1 2 3 4
1 2 5 6
3 4 5 6

4