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