English text is not available in this practice contest.
鐘星くんの今月のお小遣いの金額は,次のようなゲームで決まることになった.
たとえば,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 円である.
鐘星くんが破り捨てるカードを適切に選んだとき,今月のお小遣いは最大でいくらになるだろうか.
入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.
K s1s2...sN
1 行目には整数 K が与えられる.K は 2 以上 14 以下であることが保証される.
2 行目には文字列が与えられ,その長さが N である.N は K 以上 200,000 以下の整数であり,かつ K の倍数であることが保証される.また,この文字列の i 番目の文字 si は,はじめに左から i 番目のカードに書かれている数字であり,1 以上 9 以下であることが保証される.
入力の終わりは 1 つのゼロからなる行で表される.
各データセットに対し,鐘星くんの今月のお小遣いの最大値を表す整数を,1 行に出力せよ.
なお,この問題の制約から,答えが 263 未満であることは証明できる.ただし,32 ビット整数型では表現できない場合があることに注意せよ.
3 299792458 14 37828944296678 2 9335413296572977435242595825577315838186532253894144498711392753253512 0
1955 37828944296678 2022