Minimum Grade

Interview

Time limit1sMemory limit1024 MB

Summary

Given the grades of N-1 courses and a target GPA, find the lowest grade for the last course that makes the truncated semester average exceed the target.

Level: Easy2 of 10
Topics: Implementation, Math
Solved: No attempts yet

Statement

You are given the minimum average grade point (GPA) you must reach this semester and the grades of every course you took this semester except one. Print the lowest grade you must earn in the remaining course to meet the minimum. The grade-to-point conversion table is below.

Grade	A+	A0	B+	B0	C+	C0	D+	D0	F
Points	4.50	4.00	3.50	3.00	2.50	2.00	1.50	1.00	0.00

The semester average is the sum of (credits $\times$ points) over all courses, divided by the total credits this semester, then truncated after the second decimal place. The minimum is met only if the semester average is greater than the minimum. Floating-point types can introduce rounding errors, so take care with them.

Input

The first line contains the number of courses $N$ taken this semester and the minimum average grade point $X$ , separated by a space. ( $2 \le N \le 24$ , $0.00 \le X \le 4.50$ , and $X$ is a real number given to two decimal places.)

From the second line through the next $N - 1$ lines, each line gives the credits $c_i$ and the grade $g_i$ of one course, separated by a space. ( $1 \le c_i \le 6$ , and $g_i$ is one of A+, A0, B+, B0, C+, C0, D+, D0, F.)

The next line contains the credits $L$ of the remaining course. ( $1 \le L \le 6$ )

Output

Print the lowest grade you must earn in the remaining course to meet the minimum average grade point. If no grade can meet the minimum, print impossible.

Examples4

Example 1
Input
```
5 3.59
4 A+
3 B+
3 C+
1 D0
3
```
Expected output
```
A+
```
Example 2
Input
```
3 4.44
5 A+
4 A+
1
```
Expected output
```
A0
```
Example 3
Input
```
5 2.54
3 B+
2 B0
2 C+
2 C0
1
```
Expected output
```
F
```

Example 4

Input

5 3.60
4 A+
3 B+
3 C+
1 D0
3

Expected output

impossible