Спочатку існує \(N\) розмірів слаймів. Зокрема, для кожного \(1≤i≤N\) існує \(C_i\) ​ сллаймів розміром \(S_i\) ​.

Степан може повторювати синтез слаймів будь-яку кількість разів (можливо, нуль) у будь-якому порядку. Синтез слайму здійснюють наступним чином.

• Виберіть два слайми однакового розміру. Нехай цей розмір буде \(X\), і з’явиться новий слайм розміром \(2X\). Потім два оригінальних слайми зникають.

Степан хоче мінімізувати кількість слаймів. Яку мінімальну кількість сллаймів він може отримати за допомогою оптимальної послідовності синтезу?

Обмеження

• \(1≤N≤10^5\)
• \(1≤S_i ≤10^9\)
• \(1≤C_i ≤10^9\)
• \(S_1 ,S_2 ,…,S_N\) ​ є різними.
• Усі вхідні значення є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступні  \(N\) рядків містять цілі числа \(S_i, C_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

3
3 3
5 1
6 1

Приклад вихідних даних

3

Спочатку є три слайми розміром 3, один розміром 5 і один розміром 6.

Такахаші може виконати синтез двічі наступним чином:

• Спочатку виконайте синтез, вибравши два слайми розміром 3. Буде один розміром 3, один розміром 5 і два розміром 6.
• Далі виконайте синтез, вибравши два слайми розміром 6. Буде один розміром 3, один розміром 5 і один розміром 12.

Незалежно від того, як він повторює синтез з початкового стану, він не може зменшити кількість слаймів до 2 або менше, тому ви повинні вивести 3.

Приклад вхідних даних

3
1 1
2 1
3 1

Приклад вихідних даних

3

Приклад вхідних даних

1
1000000000 1000000000

Приклад вихідних даних

13