Обратите внимание на нестандартное ограничение по памяти.
Есть \(n\) задач, пронумерованных целыми числами от \(1\) до \(n\). У \(i\)-й задачи есть сложность \(c_i = 2^i\), тэг \(tag_i\) и счёт \(s_i\).
После задачи с номером \(i\) можно решить задачу с номером \(j\) только в том случае, если \(\text{IQ} < |c_i - c_j|\) и \(tag_i \neq tag_j\). После этого \(\text{IQ}\) меняется и становится равным \(\text{IQ} = |c_i - c_j|\) и вы набираете \(|s_i - s_j|\) очков.
Первой можно решить любую задачу. Задачи можно решать в любом порядке, каждую сколько угодно раз.
Изначально \(\text{IQ} = 0\). Найдите максимальное количество очков, которое можно набрать.
Выходные данные
Для каждого набора входных данных выведите одно число — максимальное количество очков, которое можно набрать.
Примечание
В первом наборе входных данных оптимальная последовательность решения задач такая:
- \(1 \rightarrow 2\), после этого суммарный счёт равен \(5\) и \(\text{IQ} = 2\)
- \(2 \rightarrow 3\), после этого суммарный счёт равен \(10\) и \(\text{IQ} = 4\)
- \(3 \rightarrow 1\), после этого суммарный счёт равен \(20\) и \(\text{IQ} = 6\)
- \(1 \rightarrow 4\), после этого суммарный счёт равен \(35\) и \(\text{IQ} = 14\)
Во втором наборе входных данных оптимальная последовательность решения задач такая:
- \(1 \rightarrow 2\), после этого суммарный счёт равен \(5\) и \(\text{IQ} = 2\)
- \(2 \rightarrow 3\), после этого суммарный счёт равен \(10\) и \(\text{IQ} = 4\)
- \(3 \rightarrow 4\), после этого суммарный счёт равен \(15\) и \(\text{IQ} = 8\)
- \(4 \rightarrow 1\), после этого суммарный счёт равен \(35\) и \(\text{IQ} = 14\)
В третьем наборе входных данных оптимальная последовательность решения задач такая:
- \(1 \rightarrow 3\), после этого суммарный счёт равен \(17\) и \(\text{IQ} = 6\)
- \(3 \rightarrow 4\), после этого суммарный счёт равен \(35\) и \(\text{IQ} = 8\)
- \(4 \rightarrow 2\), после этого суммарный счёт равен \(42\) и \(\text{IQ} = 12\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
1 2 3 4
5 10 15 20
4
1 2 1 2
5 10 15 20
4
2 2 4 1
2 8 19 1
2
1 1
6 9
1
1
666
|
35
30
42
0
0
|