Problem A. Judging tires ≡

Statement

According to ISO stadnard Metric tire code, tire dimensions are described by a string of letters and numbers in the following format:

• 3-digit nonzero number: The nominal section width of the tire in millimeters, the widest point from both outer edges.
• /: Slash character for separation.
• 2- or 3-digit nonzero number: The aspect ratio of the sidewall height to the nominal section width of the tire, as a percentage.
• Letter R indicating radial construction of the fabric carcass of the tire.
• 2-digit nonzero number: Diameter in inches of the wheel disk that the tires are designed to fit.

Rules of ACM (Any Car Modification) race specify a fixed tire dimensions for all participating cars. Young racer Vasya has not been able to find this type of tire. However, his car will still be approved for the race by judges only if radius of the wheel (wheel disk radius plus sidewall height) differs by at most K percent from that of the specified tire.

Note: 1 inch = 25.4 millimeters. Number a differs from b by at most c percent when 100 × |a − b| / b ≤ c.

Input file format

First line of input file contains integer K.

Second and third lines contain Metric tire codes of specified tire and Vasya's tire respectively. Tire codes contain only digits, R and slash (ASCII 47) characters.

Output file format

Output file must contain a single string — APPROVED if Vasya's car is approved to the race or DISAPPROVED otherwise.

Constraints

0 ≤ K ≤ 100

Sample tests

2
195/65R15
205/55R15

DISAPPROVED

1
195/65R15
185/070R15

APPROVED

Problem B. Aquatic life ≡

Statement

Scientists of Nearsea Institute of Underwater Life obtained a picture of the mysterious aquatic life form. They wanted to determine the creature's species.

To do that, picture copies were distributed among N experts. Each expert made G_i guesses, each guess consisting of the name of the species and the score s_ij reflecting expert's level of confidence in the guess. For each expert, all guesses name different species.

You program must choose the species which received the highest total score from all experts.

In the first sample below "Ceramaster_arcticus" species received the total score of 14.

Input file format

Input file contains integer N on the first line, followed by N line blocks — one for each expert.

Each line block contains integer G_i, on the first line, followed by G_i lines — one for each guess.

Each guess line contains an integer s_ij followed by a string — guess score and species name. Names consist of Latin letters and underscores (ASCII 95). Names are case-sensitive ("a" and "A" are different names).

Output file format

Output file must contain names of all species with the score equal to the highest total score, one name per line, sorted lexicographically.

Constraints

1 ≤ N ≤ 100, 1 ≤ G_i ≤ 100, 1 ≤ s_ij ≤ 100

Species names contain from 1 to 50 characters.

Sample tests

3
2
5 Ceramaster_patagonicus
5 Ceramaster_arcticus 
3
7 Neoferdina_insolita
1 Neoferdina_glyptodisca
1 Ceramaster_arcticus 
2
8 Ceramaster_arcticus
2 Neoferdina_insolita

Ceramaster_arcticus

2
3
5 a
6 b
1 c
2
3 a
7 c

a
c

1
4
13 a
7 b
13 B
9 A

B
a

Problem C. Easy money ≡

Statement

Young programmer Vasya was not at all interested in car races, but many of his friends were. One day, friends persuaded Vasya to come with them to a sports bar to drink beer and watch some very important race involving N cars — they told Vasya the name of the race, but he immediately forgot it.

At first Vasya was not keen to go, but the perspective of a good beer won him over.

After an hour at the bar, Vasya understood that that the endless images of the cars driving around and around were just as boring with beer as without it. His friends, however, got quite excited and started to place bets on race results. Due to the amount of beer consumed, the bets were wild and some of them did not reflect actual chances at all. In total, M bets were suggested.

Since Vasya was unable to have fun, he decided at least to make some profit. All bets are of the form "I bet A roubles versus B roubles that car p will come ahead of car q". That means betting person agrees to pay A roubles if he was wrong (i.e. q will come ahead of car p), and requires the other side to pay him B roubles if he was right.

By betting on the same cars with different friends, Vasya would in some cases guarantee himself a net win, even if he loses some of the bets. So as not to alienate too many of his friends, Vasya decided to accept only two bets.

Find two bets for Vasya which will guarantee him the largest profit in the worst case.

Input file format

Input file contains integers N M followed by M bet descriptions.

Each bet description contains integers A_i B_i p_i q_i.

Output file format

Output file must contain a single integer — the maximum amount of guaranteed profit. If there is no way to select two bets to be always profitable, output must contain 0.

Constraints

2 ≤ N, M ≤ 10000;

1 ≤ A_i, B_i ≤ 10000;

1 ≤ p_i, q_i ≤ N, p_i ≠ q_i;

Sample tests

2 2
100 10 1 2
100 10 2 1

90

3 3
200 100 1 2
40 50 2 1
100 1 1 3

0

Задача D. Супрематизм ≡

Условие

Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.

Казимир помнил, что в супрематизме картина состоит из простых фигур, поэтому, сначала он нарисовал прямоугольник n × m, составленный из разноцветных квадратов 1 × 1. После критического переосмысления своего творения, Казимир пришел к выводу, что получившаяся картина слишком сложна, и не все смогут понять его задумку. Второго холста у него не было, и он решил исправлять эту картину. На достаточно простой картине, по мнению Казимира, должен присутствовать всего один цвет.

Казимир решил исправить картину следующим образом. Он может взять строку своей картины, более половины единичных квадратов в которой покрашено в один и тот же цвет, и перекрасить всю строку в этот цвет. Аналогично он может перекрасить столбец, более половины единичных квадратов в котором покрашено в один цвет.

Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.

Формат входного файла

В первой строке заданы два числа n и m (1 ≤ n, m ≤ 300) — размеры картины. Далее, в n~строках задано по m чисел c_i,j (1 ≤ c_i,j ≤ 1 000 000) — цвета квадратов, из которых составлена картина. Гарантируется, что на картине представлено хотя бы два цвета.

Формат выходного файла

Если Казимиру не удастся сделать картину достаточно простой, выведите Poor Kazimir.

Иначе, выведите в первой строке k — количество действий, которое нужно сделать Казимиру. Действия могут быть двух видов:

• R r — перекрасить строку r (1 ≤ r ≤ n).
• C c — перекрасить столбец c (1 ≤ c ≤ m).

Разрешается сделать не более 1000 действий.

Примеры тестов

3 3
1 1 2
2 1 1
2 2 2

5
R 1
R 2
C 1
C 2
C 3

3 3
1 1 2
2 1 1
2 2 2

4
C 1
C 3
R 1
R 2

2 2
1 2
3 4

Poor Kazimir