お小遣いの最大化

English text is not available in this practice contest.

鐘星くんの今月のお小遣いの金額は,次のようなゲームで決まることになった.

  1. はじめに,N 枚のカードが横一列に並んでいる.それぞれのカードには,1 から 9 までのいずれかの数字が 1 つ書かれている.また,整数 K が指定される.ここで NK の倍数である.
  2. 鐘星くんは,これら N 枚のカードの中から,何枚かのカードを選んで破り捨てることができる.ここで,破り捨てるカードの枚数は,K の倍数でなければならない.なお,1 枚も破り捨てなくてもよいし,N 枚全部破り捨ててもよい.
  3. 残ったカードの枚数は K の倍数である.これらのカードを,順番を変えることなく,左から順に K 枚ずつのグループに分ける.
  4. それぞれのグループのカードに書かれた数字を,K 桁の十進数とみなす.これら K 桁の数をすべて足し合わせた値が,鐘星くんの今月のお小遣いの金額となる.

たとえば,N = 9, K = 3 で,カードに書かれた数字が左から順に 2, 9, 9, 7, 9, 2, 4, 5, 8 であったとする.これらのカードを 1 枚も破り捨てない場合,鐘星くんの今月のお小遣いは 299 + 792 + 458 = 1549 円である.一方,1 枚目,6 枚目,7 枚目の計 3 枚のカードを破り捨てる場合,残った 6 枚のカードに書かれた数字は左から順に 9, 9, 7, 9, 5, 8 となり,お小遣いは 997 + 958 = 1955 円となる.なお,すべてのカードを破り捨てた場合,お小遣いは 0 円である.

鐘星くんが破り捨てるカードを適切に選んだとき,今月のお小遣いは最大でいくらになるだろうか.

Input

入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.

K s1s2...sN

1 行目には整数 K が与えられる.K2 以上 14 以下であることが保証される.

2 行目には文字列が与えられ,その長さが N である.NK 以上 200,000 以下の整数であり,かつ K の倍数であることが保証される.また,この文字列の i 番目の文字 si は,はじめに左から i 番目のカードに書かれている数字であり,1 以上 9 以下であることが保証される.

入力の終わりは 1 つのゼロからなる行で表される.

Output

各データセットに対し,鐘星くんの今月のお小遣いの最大値を表す整数を,1 行に出力せよ.

なお,この問題の制約から,答えが 263 未満であることは証明できる.ただし,32 ビット整数型では表現できない場合があることに注意せよ.

Sample Input

3
299792458
14
37828944296678
2
9335413296572977435242595825577315838186532253894144498711392753253512
0

Output for the Sample Input

1955
37828944296678
2022