Wings loves playing Lego!
Wings loves playing Lego! Today, Wings is playing a strange set of Lego blocks. There are n symmetrical elongated blocks in this set. For some blocks, the number of bottom slots is not equal to the number of top slots. The picture below shows examples of such blocks. Wings sorts these blocks so that the number of bottom slots is in non-decreasing order and numbers them from 1 to n. He also notices that the number of top slots is in non-increasing order. Wings wants to pick m blocks for his building. He fifirst picks the block p1, places it on the table. In the following time, he picks the block pi (pi > pi−1), and puts it on block pi−1. Wings can assemble two blocks horizontally or vertically. The picture below shows all the different ways of assembling two certain blocks. Note that even the fifirst can be rotated to get the third, but the whole stack may not be symmetric, so we consider it to be assembled differently. The same goes for the fourth and seventh, and the fififth and sixth. However, when Wings picks one block, and there are k different ways of assembling, it will take him k seconds to decide how to assemble. Wings wants to know the earliest time he can complete his building.
