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 <= S <= 10^9$
$1 <= D_i <= 10^9$
$1 <= R_i <= 10^9$
*Subtask 1* (35 points):
$1 <= N <= 16$
*Subtask 2* (35 points):
$1 <= N <= 1000$
*Subtask 3* (30 points):
$1 <= N <= 2 dot.op 10^5$
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.
## Input
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.
## Output
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.
[samples]
## Scoring
$1 <= S <= 10^9$$1 <= D_i <= 10^9$$1 <= R_i <= 10^9$*Subtask 1* (35 points):$1 <= N <= 16$*Subtask 2* (35 points):$1 <= N <= 1000$*Subtask 3* (30 points):$1 <= N <= 2 dot.op 10^5$
## Note
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.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of bosses.
Let $ S \in \mathbb{Z}^+ $ be Cindy’s initial stamina.
Let $ D = (D_1, D_2, \dots, D_N) $ be the sequence of boss difficulties.
Let $ R = (R_1, R_2, \dots, R_N) $ be the sequence of potion restorations.
**Constraints**
1. $ 1 \leq S \leq 10^9 $
2. $ 1 \leq D_i \leq 10^9 $ for all $ i \in \{1, \dots, N\} $
3. $ 1 \leq R_i \leq 10^9 $ for all $ i \in \{1, \dots, N\} $
4. Bosses must be defeated in order: boss $ i $ can only be challenged after defeating bosses $ 1 $ through $ i-1 $.
5. Upon defeating boss $ i $, Cindy gains access to potion $ R_i $, which may be used at any later time (at most once).
6. Stamina is non-negative at all times.
**Objective**
Simulate traversal through bosses $ 1 $ to $ N $ in order:
- At step $ i $, if current stamina $ \geq D_i $, defeat boss $ i $, deduct $ D_i $ from stamina, and add $ R_i $ to available potions.
- If current stamina $ < D_i $, use the largest available unused potions (greedily) to restore stamina until either:
- Stamina $ \geq D_i $, then defeat the boss and proceed;
- No more potions can restore sufficient stamina → stop.
Let $ k $ be the maximum number of bosses defeated.
- If $ k = N $:
Output:
```
WIN
m
```
where $ m $ is the **minimum number of potions consumed** to defeat all bosses.
- If $ k < N $:
Output:
```
LOSE
k
```
**Note**: To minimize potion consumption while ensuring success, use a greedy strategy: when lacking stamina to defeat boss $ i $, use the largest available potions first (maximize stamina gain per potion used). Track used potions and maintain a max-heap of available potion values.