CF353C Find Maximum

Valera has array $ a $ , consisting of $ n $ integers $ a_{0},a_{1},...,a_{n-1} $ , and function $ f(x) $ , taking an integer from $ 0 $ to $ 2^{n}-1 $ as its single argument. Value $ f(x) $ is calculated by formula , where value $ bit(i) $ equals one if the binary representation of number $ x $ contains a $ 1 $ on the $ i $ -th position, and zero otherwise. For example, if $ n=4 $ and $ x=11 $ $ (11=2^{0}+2^{1}+2^{3}) $ , then $ f(x)=a_{0}+a_{1}+a_{3} $ . Help Valera find the maximum of function $ f(x) $ among all $ x $ , for which an inequality holds: $ 0

The first line contains integer $ n $ $ (1

Print a single integer — the maximum value of function $ f(x) $ for all .

In the first test case $ m=2^{0}=1,f(0)=0,f(1)=a_{0}=3 $ . In the second sample $ m=2^{0}+2^{1}+2^{3}=11 $ , the maximum value of function equals $ f(5)=a_{0}+a_{2}=17+10=27 $ .