Eric has just bought a new game for his NES, called Battletoads. The objective of the game is to defeat the Dark Queen and her army of space mutants.

After spending a long time trying to beat the game, he realized that it was very difficult to kill the Dark Queen because his character had no weapons and needed to defeat her using only punches.

Frustrated by not being able to defeat the game's final boss, Eric decided to develop a new game, which he named Battlefrogs. In this game, the final boss is called Light Queen and the playable characters are always equipped with a laser weapon. The weapon works as follows:

Let $$$E$$$ be the weapon's energy.

• If $$$E \gt 0$$$, Eric can fire a laser beam and $$$E$$$ decreases by one unit. If Eric fires the beam at a space mutant, the mutant will die, and if he fires the beam at the Light Queen, her life decreases by one unit.
• If $$$E \le 0$$$, Eric can still fire a laser beam and $$$E$$$ decreases by one unit. However, if Eric fires the beam at a space mutant, the mutant will die, but if he fires the beam at the Light Queen, her life will not be affected.

Before reaching the Light Queen's level, Eric must pass through $$$N$$$ levels numbered from $$$1$$$ to $$$N$$$, starting from level $$$1$$$. Each level contains $$$s_i$$$ space mutants on the way and an energy bank with power $$$e_i$$$ that charges his weapon by $$$e_i$$$ units. Additionally, at the start of each level, there is an alternative route with a wormhole guarded by $$$X$$$ space mutants that allows Eric to skip $$$k$$$ levels ahead.

If Eric uses the wormhole at level $$$i$$$, he immediately jumps to level $$$i+k$$$, or, if the $$$(i+k)$$$-th level does not exist, to the Light Queen's level. When using the wormhole, Eric does not need to kill any of the $$$s_i$$$ mutants, but he will not be able to charge his weapon by $$$e_i$$$ units and is required to kill the $$$X$$$ mutants guarding the wormhole. If he decides not to use the wormhole at level $$$i$$$, he must defeat the $$$s_i$$$ space mutants, will be able to increase his weapon's energy by $$$e_i$$$ units, and will proceed to level $$$(i + 1)$$$, or to the Light Queen's level if the $$$(i + 1)$$$-th level does not exist.

Knowing that the Light Queen dies when her life reaches $$$0$$$ and that Eric's weapon starts with $$$0$$$ energy, he is now thinking about balancing the game and needs to decide how much life to assign to the final boss. He asked you: what is the maximum amount of life the Light Queen can have so that it is still possible to defeat her?