На столе лежат n монеток. Некоторые из них лежат вверх решкой, а некоторые – гербом. Определите минимальное число монеток, которые нужно перевернуть, чтобы все монетки были повернуты вверх одной и той же стороной.

«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.

У Белоснежки \(n\) гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать \(i\)-го гнома нужно \(a_i\) минут, и после этого он будет спать ровно \(b_i\) минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.

Например, пусть есть всего два гнома, \(a_1\) = 1, \(b_1\) = 10, \(a_2\) = 10, \(b_2\) = 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены \(n\) кружочков, помеченных числами от 1 до \(n\). Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек \(b\) разрешено проводить, если выполнены два условия:

1. еще нет стрелочки из \(a\) в \(b\);

2. нельзя дойти по стрелочкам из \(b\) в \(a\).

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

Проигрывает тот, кто не может сделать ход.

Петя решил написать программу, играющую в эту игру. Для этого он хочет сначала посчитать, сколько различных позиций может получиться на доске.

Паук и паучиха плывут по озеру на двух веточках. Плавать они не умеют, поэтому смогут встретиться только тогда, когда веточки соприкоснутся.

Считая, что веточки имеют форму отрезков, и что они плывут с постоянными скоростями, определите, сколько осталось ждать встречи несчастным членистоногим.

Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение \(A\), составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение \(B\).

Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.

Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении \(A\), совпадает с набором спичек, используемым в изображении \(B\). Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).

Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений \(A\) и \(B\) и должна найти минимальное количество спичек, которые надо переложить в изображении \(A\), чтобы полученная картинка получалась из \(B\) параллельным переносом.