E. Extracting Pollen
time limit per test
0.6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

The first line contains two integers $$$N$$$ ($$$1 \le N \le 10^6$$$) and $$$K$$$ ($$$1 \le K \le 10^9$$$), 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 \le F_i \le 10^6$$$ for $$$1 \le i \le N$$$) denotes the initial quantity of pollen grains of the $$$i$$$-th flower.

Output

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

Examples
Input
5 3
22 15 7 2 1
Output
6
Input
3 10
21 21 21
Output
0
Input
3 9
21 21 21
Output
9