407871: GYM102911 G Gamer Girl Gauntlet

Cindy is excited to play the new video game based on the classic anime, Sort Art Online. The game is thankfully only an adaptation of the first arc, which is a normal computer-science-based MMORPG—no magic or guns. Many people justifiably consider Sort Art Online to be "one of the worst animes of all time" for a myriad of different reasons, but Cindy will always defend the first arc as being better than people give it credit for. The rest of the show is pretty bad, though.

She heard Alice really liked one of the recent arcs, so that's something, she supposes. Alice is the only reason why she's playing this game, anyway.

Anyway, Cindy is going to attempt the gauntlet, which is a post-game dungeon which requires her to defeat all of the bosses from the main story without any breaks in between. The gauntlet consists of $$$N$$$ different floors, each with an extra tough boss that must be defeated in order to reach the next floor. The bosses have difficulty $$$D_1$$$, $$$D_2$$$, $$$\dots$$$, $$$D_N$$$, given in the order Cindy must defeat them. Cindy begins the gauntlet with $$$S$$$ stamina. She can only challenge the $$$i$$$th boss once she has defeated all the bosses that come before it. She can only defeat the $$$i$$$th boss if she has at least $$$D_i$$$ stamina, and defeating the boss will deduct $$$D_i$$$ stamina from her total.

The only way Cindy can restore her stamina is by using potions. She may not bring any potions into the game mode, but each boss drops one such potion upon defeat which she can use. The potion dropped by the $$$i$$$th boss will restore $$$R_i$$$ stamina to Cindy if she chooses to use it. At any time, she can use any of the potions that were dropped by a boss she had already defeated (but she doesn't have to). Each potion can only be used at most once.

The potions are valuable loot which Cindy can sell for better gear. Thus, Cindy wants to know what is the minimum number of potions she needs to consume in order to defeat all $$$N$$$ bosses, if it is possible for her to beat all the bosses at all. If it is not possible, instead output the maximum number of bosses she can beat before running out of stamina.

The first line of input contains two space-separated integers $$$N$$$ and $$$S$$$, which are the number of bosses and Cindy's initial stamina, respectively.

The second line of input contains $$$N$$$ space-separated integers $$$D_1, D_2, \dots, D_N$$$, where $$$D_i$$$ is the difficulty of the $$$i$$$th boss.

The third line of input contains $$$N$$$ space-separated integers $$$R_1, R_2, \dots, R_N$$$, where $$$R_i$$$ is the health restored by the potion dropped by the $$$i$$$th boss.

If Cindy can beat all the bosses, first output a single line containing the word WIN, followed by another line containing the minimum number of potions she needs to consume in order to beat all the bosses.

If Cindy cannot beat all the bosses, first output a single line containing the word LOSE, followed by another line containing the maximum number of bosses that Cindy can beat before running out of stamina.

$$$1 \leq S \leq 10^9$$$

$$$1 \leq D_i \leq 10^9$$$

$$$1 \leq R_i \leq 10^9$$$

Subtask 1 (35 points):

$$$1 \leq N \leq 16$$$

Subtask 2 (35 points):

$$$1 \leq N \leq 1000$$$

Subtask 3 (30 points):

$$$1 \leq N \leq 2 \cdot 10^5$$$

4 5
2 3 4 5
3 1 9 9

WIN
3

4 1
1 90 10 1
1 99 88 101

LOSE
1

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

WIN
2

In the first sample test case, Cindy beats the first and second bosses and is left with $$$5-(2+3)=0$$$ stamina. In order to defeat the third boss, she needs to drink the potions dropped by the first two bosses. Then, to defeat the fourth boss, she needs to drink the potion dropped by the third boss. She does not need to drink the potion dropped by the fourth boss. In total, she needs to consume at least $$$3$$$ potions in order to beat all the bosses.

Note that if Cindy could have challenged the third boss first, then she could have finished the gauntlet by drinking only one potion. Unfortunately, Cindy is forced to challenge the bosses in the given order.

In the second sample test case, Cindy can only defeat the first boss, then gets stuck immediately. She loses, having beaten $$$1$$$ boss only.