408726: GYM103274 D Delivering Pizza

Jaime's pizza delivery has been awarded the "Best pizza in town" award. This is because of the care and effort they put for each pizza they make and deliver, always making sure they do not start a pizza until all pizzas before are done. However, a consultant has identified making a pizza at a time delays delivery, and waiting times have been increased considerably since they got the award because more and more people are willing to try this famous pizza.

Pizzas at Jaime's pizzas have at most 4 ingredients, $$$i_1$$$, $$$i_2$$$, $$$i_3$$$, $$$i_4$$$, and they are always done following this order, that is a pizza will never get the ingredient $$$i_3$$$ before ingredient $$$i_2$$$. When a customer orders a pizza, they write a note with the amount of each ingredient they wants in their pizza. If they don't like a specific ingredient from the list, they just write a $$$0$$$ for it. For example, if a customer requested the pizza "1 1 0 2", it means the pizza should have one unit of $$$i_1$$$, one unit of $$$i_2$$$ and two units of $$$i_4$$$. When the kitchen gets this order, Jaime will put $$$i_1$$$ in the pizza, then $$$i_2$$$, and finally $$$i_4$$$, $$$i_3$$$ is not added to the pizza as it was not requested.

To make the process faster, Jaime decided to hire $$$4$$$ people, one to work with each ingredient. These people will put in a pizza only the ingredient they were assigned to. Jaime believes in this way they can deliver pizzas faster, as, in some point, each of the recent hires will be working on a pizza, but they will always make sure to start the orders in the order they were received, and to put the ingredients in the order they should be.

Knowing that an employee takes $$$1$$$ unit of time to put $$$1$$$ unit of ingredient, and the description of the $$$N$$$ orders received in a night, can you determine the minimum amount of time it will take for all the pizzas to be delivered?

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the number of orders for the night. Each of the next $$$N$$$ lines contains $$$4$$$ integers separated by a space, where the $$$j$$$-th integer in the line will represent the amount of ingredient $$$i_j$$$ for that pizza order. Each pizza will have at most $$$10^5$$$ units of each ingredient.

Print a line with a single integer, the minimum amount of time required to deliver all pizzas.

3
10 25 15 0
0 0 25 10
5 15 10 10

70

3
10 25 15 0
0 0 25 10
0 15 10 10

55