Герой нашего повествования Валерий и его лучший друг Аркадий еще только учатся в школе, и поэтому все свободное время они проводят играя в пошаговую стратегию «GAGA: Go And Go Again». Процесс игры выглядит следующим образом.
На игровом поле располагаются две армии, каждая из которых состоит из n солдат (n всегда четное). Текущий игрок указывает для каждого своего солдата, в какого солдата противника тот будет стрелять, а после этого все солдаты игрока стреляют одновременно. Это игровой мир, и поэтому каждый солдат стреляет идеально, то есть абсолютно всегда попадает в указанную цель. Если в солдата противника стреляли, он обязательно погибает. Может случиться, что нескольким солдатам была указана одна и та же цель. Убитые солдаты больше не принимают участия в игре.
Игра «GAGA» состоит из трех шагов: сначала делает ход Валерий, потом Аркадий, после чего опять Валерий, — и игра заканчивается.
Вас попросили подсчитать, какое максимальное суммарное количество солдат может быть убито в процессе игры?
Примечание
Первый пример из условия:
1) Солдаты Валерия с номерами 1 и 2 стреляют в солдата Аркадия с номером 1.
2) Солдат Аркадия с номером 2 стреляет в солдата Валерия с номером 1.
3) Солдат Валерия с номером 1 стреляет в солдата Аркадия с номером 2.
Всего убито 3 солдата: солдат Валерия с номером 1 и солдаты Аркадия с номерами 1 и 2.