Дореми живёт в стране, состоящей из \(n\) городов, пронумерованных от \(1\) до \(n\), причём в \(i\)-м городе живёт \(a_i\) человек. Страну можно смоделировать в виде неориентированного графа с \(n\) вершинами.
Изначально в графе нет рёбер. Дореми хочет сделать граф связным.
Для этого она может добавить ребро между \(i\) и \(j\), если
\(\) \sum_{k \in S} a_k \ge i\cdot j \cdot c, \(\)
где \(S\) — множество всех вершин, которые в данный момент находятся в одной компоненте связности либо с \(i\) или с \(j\), а \(c\) — фиксированная константа.
Может ли Дореми сделать граф связным?
Две вершины \((i, j)\) находятся в одной компоненте связности, если существует путь из \(i\) в \(j\). Граф является связным, если все его вершины находятся в одной компоненте связности.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если возможно сделать граф связным, и «NO» (без кавычек) в противном случае.
Буквы можно выводить в любом регистре (верхнем или нижнем).
Примечание
В первом наборе входных данных Дореми может добавлять ребра в следующем порядке:
- Добавить \((1,2)\). Эта операция допустима, так как \(a_1 + a_2 = 20 \ge i\cdot j \cdot c = 20\).
- Добавить \((1,3)\). Эта операция допустима, так как \(a_1 + a_2 + a_3 = 35 \ge i \cdot j \cdot c = 30\).
- Добавить \((1,4)\). Эта операция допустима, так как \(a_1 + a_2 + a_3 + a_4 = 45 \ge i \cdot j \cdot c = 40\).
Во втором наборе входных данных Дореми может добавить ребро \((1,2)\), так как \(a_1 + a_2 =2 \ge 1 \cdot 2 \cdot 1\). После этого граф становится связным.
В третьем наборе входных данных Дореми может добавлять ребра в порядке \((5,4)\), \((5,3)\), \((5,2)\) и \((5,1)\).
В четвертом наборе входных данных Дореми вообще не может добавить ни одного ребра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2
|
Yes
Yes
Yes
No
No
Yes
No
|