29990번 - Extracting Pollen 다국어

문제

Spring has arrived, ushering in a season of hard work at the Swarm of Bees Company (SBC). With the blooming of N beautiful flowers in the garden, each flower boasts a certain quantity of pollen grains. The SBC enforces strict rules to keep the bees industrious in their pollen collection.

1. The first rule pertains to the amount of pollen grains collected: when a bee visits a flower, it must gather the sum of the digits in its current pollen quantity. For instance, if a bee visits a flower with 123 pollen grains, it must collect 1 + 2 + 3 = 6 grains, leaving the flower with 123 − 6 = 117 grains. Similarly, if the flower holds 201 grains, the bee must gather 2 + 0 + 1 = 3 grains, leaving 198 grains remaining.
2. All bees must form a queue at the start of the day; the bee at the front of the queue must collect pollen from one of the flowers with the largest amount pollen. If a bee visits a flower with 0 grains of pollen, it collects zero grains. After collecting pollen from a flower, the bee ends its shift and returns to the hive.

Gertrude finds these rules bewildering and seeks help to determine the pollen amount she must collect when it’s her turn. Getrude has amazingly sharp sight and noticed that she is currently the K-th bee in the SBC-defined order.

입력

The first line contains two integers N (1 ≤ N ≤ 10⁶) and K (1 ≤ K ≤ 10⁹), representing the number of flowers and Gertrude’s position in the bee line, respectively. The second line contains N integers, where the i-th integer F_i (1 ≤ F_i ≤ 10⁶ for 1 ≤ i ≤ N) denotes the initial quantity of pollen grains of the i-th flower.

출력

Output a single integer Q representing the amount of pollen Gertrude will collect.

제한

힌트