Каждое воскресенье Андрей вместе с друзьями играет в футбол. На каждую игру приходит одно и то же (чётное) количество человек. Когда друзья собираются, первым делом они начинают обсуждать, как им разделиться на две команды.

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

Чтобы не было новых споров и обид, капитаны по очереди выбирают по одному игроку среди тех, кто ещё не включён в какую-либо команду. Каждый капитан стремится набрать как можно более сильную команду и потому выбирает самого сильного среди ещё не выбранных игроков. Сила игрока — это целое число от 1 до 100 (как в FIFA). Сила команды вычисляется как суммарная сила всех игроков в этой команде, включая капитана.

Андрею стало интересно, какой может быть минимальная разница в силе между командами. Но он очень занят подготовкой контеста по программированию, поэтому просит вас найти эту величину.

На всякий случай ещё раз напомним, что в роли капитанов могут оказаться два любых игрока, не обязательно самые сильные.