Statement

Anna really likes tulips. She has N tulips in her garden, numbered from 0 to N-1. The beautiness of tulip i is T_i. She wants to create K (non-empty) bouquets from the tulips. To do that, she starts to walk from the first tulip towards the last. At each flower, she can either (1) insert it into the current bouquet, or (2) finish the current bouquet and start a new one. The current tulip is added to the new bouquet. Note that, after finishing a bouquet she won't be able to insert more tulips into it! The beautiness of a bouquet is the minimum of the beautinesses of the tulips in it. She wants to maximize the sum of the beautinesses of the K bouquets by partitioning the tulips optimally. Your task is to calculate this maximum value!