Tire Tug

Interview

Time limit1sMemory limit1024 MB

Summary

Distribute M students across N tires, beating the opponent's count on chosen tires to maximize the score gap and report whether a win, draw, or loss is the best outcome.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Sorting, Prefix sum
Solved: No attempts yet

Problem

Tire tug is a popular event at the Gyeonggi Buk Science High School sports day.

The rules are as follows.

There are $N$ tires, and the $i$ -th tire has a score of $S_i$ .
For each tire, both teams assign a number of people to pull that tire.
For each tire, the team that assigns more people gains $S_i$ points. If the two teams assign the same number of people, neither team gains points for that tire.
The team with the higher total score wins.

As the brain of Class 1-1, you have learned through a spy how many people Class 1-2, the opposing team, assigned to each tire.

Given the number of tires $N$ , the number of students in Class 1-1 $M$ , the score of each tire, and the number of people Class 1-2 assigned, determine whether Class 1-1 can win.

Input

The first line gives the number of tires $N$ and the number of students in Class 1-1 $M$ .

The next $N$ lines give the score $S_i$ of the $i$ -th tire and the number of students $P_i$ that Class 1-2 assigned to that tire.

All given numbers are positive integers.

Output

Print W if Class 1-1 can win, D if a draw is the best possible result, and L if Class 1-1 loses no matter what.

Constraints

$1 \le N \le 100$
$1 \le M \le 100\,000$
$1 \le S_i, P_i \le 100\,000$

Examples2

Example 1
Input
```
2 3
10 2
5 2
```
Expected output
```
W
```
Example 2
Input
```
3 4
10 4
6 1
7 2
```
Expected output
```
L
```