Sherlock Holmes

Time limit1sMemory limit128 MB

Summary

Split n boxes into two equal groups so that one ball color is a strict majority in both groups, and output that color with the maximum of the smaller group's majority percentage, or report no solution.

Level: Medium6 of 10
Topics: Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

Sherlock Holmes, the well-known detective, must solve a tricky situation. He has $n$ boxes $B_1, B_2, \dots, B_n$ (where $n$ is even), each containing exactly $m$ balls. The balls are white or black. A box $B_i = (W_i, B_i)$ contains $W_i$ white balls and $B_i$ black balls (so $W_i + B_i = m$ ).

He must partition the boxes into two groups of $n/2$ boxes each, so that either the white balls or the black balls form a majority (strictly more than half of that group's balls) in both groups. If such a color exists, let $m_1$ and $m_2$ be the percentage of the majority color's balls in each group. Holmes must find the maximum possible value of $\min(m_1, m_2)$ . Can you help him?

Input

The input consists of several data sets, each describing one collection of boxes. A data set starts with the number of boxes $n$ ( $n < 10000$ ). Then comes the number of balls $m$ ( $m < 10000$ ) contained in each box, followed by, for every box, the number of white balls and the number of black balls (each $< 10000$ ) in this order. All numbers may be separated by arbitrary white space. The input is always correct and terminates at end of file.

Output

For each data set, print the result on its own line. If a majority color exists, print that color (W for white, B for black), a single space, and the maximum value of $\min(m_1, m_2)$ rounded to two decimal places. Otherwise print No solution.

Examples4

Example 1
Input
```
4
30
17 13
12 18
20 10
14 16
```
Expected output
```
W 51.67
```
Example 2
Input
```
4
30
13 17
18 12
10 20
16 14
```
Expected output
```
B 51.67
```
Example 3
Input
```
2
10
6 4
6 4
```
Expected output
```
W 60.00
```
Example 4
Input
```
4
5
5 0
5 0
5 0
5 0
```
Expected output
```
W 100.00
```