Как-то раз, туманным Стокгольмским утром, Карлсон решил подкрепиться запасами варения в доме своего друга — малыша Свантесона. К счастью для Карлсона в доме его друга не оказалось никого. Голодным Карлсон оставаться был не намерен, так что решил самостоятельно найти себе еду в доме малыша Свантесона.

Взгляд Карлсона сразу же пал на n деревянных шкафов, стоящих на кухне. Он тут же догадался, что в этих шкафах спрятаны заветные запасы варенья. Карлсон с жадностью стал летать по кухне, открывать и закрывать дверцы шкафов, хватать и опустошать все банки с вареньем, которые ему удавалось найти.

И вот, все банки с вареньем пусты, Карлсон наелся и не хочет оставлять следов своего пребывания, чтобы не подводить своего друга. Каждый из шкафов имеет две дверцы: левую и правую. Карлсон помнит, что когда он примчался на кухню, левые дверцы всех шкафов были в одинаковом положении (открыты или закрыты), аналогично все правые дверцы шкафов также были в одинаковом положении (открыты или закрыты). Карлсон хочет, чтобы к моменту появления дома хозяев это условие также выполнялось. Карлсон не помнит, в каком именно положении находились все левые дверцы, также он не помнит в каком положении находились все правые дверцы. Поэтому ему неважно в каком именно положении будут все левые или правые дверцы. Главное — чтобы все левые дверцы были в одинаковом положении и все правые дверцы были в одинаковом положении. Например, все левые дверцы могут быть закрыты, а все правые — открыты.

За одну секунду Карлсон может открыть или закрыть одну дверцу какого-либо шкафа. Он понимает, что до прихода хозяев осталось очень мало времени, поэтому хочет знать минимальное количество секунд t, за которое он сможет привести дверцы всех шкафов в нужное ему положение.

Ваша задача — написать программу, которая определит искомое количество секунд t.