• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

محمدجواد که پشت‌کار بالایی دارد، مسئول برگزاری جام حذفی برنامه‌نویسی شده است. همانطور که از اسمش پیداست این مسابقات قوانین عجیب و غریبی هم دارند. در این مسابقات $2^n$ تیم شرکت می‌کنند که تیم $i$م ، به اندازه‌ی$p_i$ قدرت کدزدن دارد. در هر مرحله از مسابقه محمدجواد تیم‌های حاضر را به دو دسته تقسیم می‌کند که دسته‌ی اول به ترتیب نصفه‌ی اول تیم‌های باقی‌مانده هستند و دسته‌ی دوم نصفه‌ی دوم. سپس محمدجواد به هر دسته پروژه‌ای می‌دهد و تصمیم می‌گیرد که با یک دسته خداحافظی کرده و با دسته‌ی دیگر ادامه دهد و به پرقدرت ترین تیم دسته‌ی از دست رفته به اندازه‌ی قدرتش جایزه دهد. محمدجواد دوست دارد بیشترین جایزه‌ی ممکن را به شرکت کنندگان بدهد. برای همین از شما کمک می‌خواهد که به او بگویید چه مقدار پول باید از سرمایه‌گذار دریافت کند. دقت کنید که محمدجواد به تیم آخر نیز جایزه خواهد داد.

به عنوان مثال اگر ۸ تیم وجود داشته باشد که قدرت هایشان برابر 1 6 1 7 1 8 1 4 باشد، محمد جواد می‌تواند در مرحله‌ی اول با ۴ تیم اول(تیم‌های با شماره ۱ و ۲ و ۳ و ۴) خداحافظی کرده و به اندازه ۸تا به تیم شماره ۳ جایزه دهد سپس با ۲ تیم دسته‌ی دوم (تیم‌های با شماره ۷ و ۸) خداحافظی کرده و ۶تا به تیم شماره‌ ۷ جایزه دهد و در مرحله ی بعد با تیم شماره ۵ خداحافظی کرده و ۷تا به او جایزه بدهد و در انتها به تیم شماره ۶ نیز ۱ی جایزه دهد که در مجموع می‌شود ۸ +‌ ۶ + ۷ + ۱ = ۲۲ او می‌تواند به جای روش بالا به ترتیب با ۴ تیم دوم خداحافظی کرده سپس با تیم سه و چهار و بعد از آن با تیم یک خداحافظی کند. که در این صورت باید به اندازه ۷ +‌ ۸ +‌ ۴ +‌ ۱ = ۲۰ تا جایزه دهد که یعنی روش اول بهتر بود.

ورودی

در سطر اول ورودی $n$ آمده است که نشان‌دهنده‌ی تعداد مراحل است.

در خط بعدی $2^n$ عدد آمده است که عدد $i$م نشان‌دهنده‌ی $p_i$ است.

$$ 1 \le n \le 17 $$ $$ 1 \le p_i \le 1\ 000\ 000\ 000 $$

خروجی

خروجی شامل یک عدد است، که نشان‌دهنده‌ی مجموع پولیست که محمدجواد باید هدیه بدهد.

مثال

ورودی نمونه ۱

2
1 2 3 4

خروجی نمونه ۱

9

ورودی نمونه ۲

3
1 6 1 7 1 8 1 4

خروجی نمونه ۲

22