Четыре Всадника проникают в сейф, где хранятся драгоценности. В сейфе лежат $n$ слитков золота массами $a_1, a_2, ..., a_n$.

Из-за системы безопасности они не могут просто взять всё: при выходе сработает детектор, если количество оставшихся там слитков будет меньше количества слитков, вынесенных из сейфа. 

Но Всадники не даром лучшие в своём деле, а потому решили перехитрить даже систему безопасности: находясь внутри сейфа, они могут взять любой слиток и разделить его на два новых слитка ненулевой целой массы, причём каждый из получившихся слитков можно затем поделить ещё таким же образом. В результате количество слитков в сейфе увеличится и они смогут вынести больше золота!

К сожалению, их проникновение уже засекли, и до того как их поймают, они успеют сделать не более $k$ разделений слитков. У Всадников очень мало времени, а золото упускать не хочется, поэтому им необходимо как можно скорее узнать, какое максимальное количество золота они смогут вынести из сейфа.