Монокарп играет в стратегическую компьютерную игру, в которой он развивает город. Город населяют существа четырёх разных рас — люди, эльфы, орки и гномы.
У каждого жителя города есть настроение, которое выражается целым числом. Оно зависит от того, какие расы и в каком количестве населяют город. А именно: настроение каждого жителя по умолчанию равно \(0\); оно повышается на \(1\) за каждого другого жителя той же расы и понижается на \(1\) за каждого жителя враждебной расы. Люди враждуют с орками, а эльфы — с гномами.
В начале игры город Монокарпа никто не населяет. За игру к нему будет \(n\) раз приходить группа существ, желающих поселиться в его городе. В \(i\)-й группе \(a_i\) людей, \(b_i\) орков, \(c_i\) эльфов и \(d_i\) гномов. Каждый раз Монокарп может либо принять в город всю группу существ, либо отклонить (также всю группу).
Игра рассчитывает количество очков, которое набирает Монокарп, по формуле \(m + k\), где \(m\) — это количество жителей города, а \(k\) — суммарное настроение всех жителей.
Помогите Монокарпу набрать максимальное количество очков в конце игры!
Выходные данные
Выведите одно число — максимальное количество очков, которое может набрать Монокарп. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит \(10^{-9}\). То есть если ваш ответ — \(a\), а ответ жюри — \(b\), то решение будет засчитано, если \(\frac{|a-b|}{\max(1,|b|)} \le 10^{-9}\).
Обратите внимание, что правильный ответ всегда целый, но он может не помещаться в \(64\)-битные целочисленные типы данных, поэтому вы можете вывести ответ как нецелое число.
Примечание
В первом примере лучшим вариантом действий будет принять все группы.
Во втором примере лучшим вариантом действий будет принять группы \(2\) и \(3\), а отклонить группы \(1\) и \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 0 1 0
1 3 4 2
2 5 1 2
4 5 4 3
1 4 4 5
|
85
|
|
2
|
4
3 3 1 5
5 1 5 3
4 4 4 1
1 3 4 4
|
41
|