Заданы \(2n\) наборов \((a, b, c)\), где \(a\) и \(b\) — некоторые положительные целые числа, а \(c\) — скобка '(' или ')'. В ровно \(n\) наборах \(c = \)'(', в остальных \(n\) — \(c =\) ')'.
Требуется выбрать два положительных числа \(x\) и \(y\) (\(x > 0\) и \(y > 0\); не обязательно целые) и отсортировать наборы в порядке возрастания \(a \cdot x + b \cdot y\). Если у нескольких наборов одно и то же значение, то их можно расположить в произвольном порядке друг между другом.
Можно ли выбрать такие значения \(x\) и \(y\), что, взяв скобки \(c\) из наборов в полученном порядке, мы получим правильную скобочную последовательность?
Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+».
Выходные данные
На каждый набор входных данных выведите «YES», если возможно выбрать такие значения \(x\) и \(y\), что, взяв скобки \(c\) из наборов в полученном порядке, мы получим правильную скобочную последовательность. Иначе выведите «NO».
Примечание
В первом наборе входных данных можно выбрать \(x = 10, y = 0.1\). Значения для наборов тогда будут \(10 \cdot 1 + 0.1 \cdot 4 = 10.4\) и \(10 \cdot 2 + 0.1 \cdot 3 = 20.3\). Тогда сначала будет первый набор, за ним второй, из чего получается скобочная последовательность «()», которая является правильной.
Во втором наборе невозможно выбрать такие положительные \(x\) и \(y\), что открывающей скобке будет присвоено значение, меньше или равное значению закрывающей скобки.
В четвертом наборе можно выбрать \(x = 0.6, y = 0.55\). Скобочная последовательность будет «(()(()))».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1 4 (
2 3 )
1
1 2 )
3 4 (
4
16 5 (
12 3 (
19 6 )
4 10 )
3 10 )
19 11 (
19 7 )
7 14 (
4
16 8 (
11 9 )
20 10 )
20 19 )
2 13 (
18 7 (
15 19 )
5 6 (
|
YES
NO
NO
YES
|