018-D.md

Худалдагч Боб

Түрүү жил Боб санах ойн чип зарж орлого олов. $n$ ѳдрийн туршид ѳдѳр бүр дараах хоёр үйл явдлын нэг нь болсон:

• Үйлчлүүлэгч Бобоос $2^x$MB багтаамжтай чип зарах эсэхийг асуухад Бобд тийм чип байвал $2^x$ тѳгрѳгѳѳр зарна.

• Програмчлалын тэмцээнд түрүүлж $2^x MB$ багтаамжтай чипээр шагнуулна.

Боб нэгээс илүү чип ѳѳртѳѳ хадгалдаггүй. Мѳн ижил үнэтэй чип асуусан үйлчлүүлэгчид байгаагүй. Тэгвэл $n$ ѳдрийн дараа Бобын олох мѳнгѳний хэмжээ хамгийн ихдээ хэд байх вэ?

Оролт

Эхний мѳрѳнд ѳдрийн тоо болох бүхэл тоо $n, (1 ≤ n ≤ 5000)$. Дараагийн $n$ мѳрѳнд тухайн ѳдрийн болсон явлыг илэрхийлнэ. Тухайн ѳдѳр үйлчлүүлэгч $2^x$MB санах ойн чип авах хүсэлт илэрхийлсэн бол $sell x$ байна. Тухайн ѳдѳр Боб $2^x$MB санах ойн чип хожсон бол $win x$ байна. Энд $x$ нь $(0 ≤ x ≤ 2000)$ байх бүхэл тоо.

Гаралт

Бобын олж болох хамгийн их мѳнгѳний хэмжээ.

-- Sugardorj