문제

길이가 인 문자열 가 주어진다. 플레이어는 문자열 를 서로 겹치지 않는 개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가  이상이어야 하며, 원래 문자열에서 연속해야 한다.

문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다.

• 문자열 를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 라고 한다.
• 나누어진 개의 문자열이 각각 에서 번째로 등장하는 문자열이라면, 얻을 수 있는 점수는  이다.

예를 들어, abcd 라는 문자열을 개의 부분문자열로 나누는 방법은 {a, b, cd}, {a, bc, d}, {ab, c, d} 의 세 가지가 있다. 여기서 부분문자열을 중복 제거하고 사전 순서로 정렬한 결과 는 a, ab, b, bc, c, cd, d 이다. 이때 {ab, c, d} 로 문자열을 나눈 경우 얻을 수 있는 점수는 점이고, 얻을 수 있는 최대 점수이다.

문자열 를 개의 부분문자열로 나눴을 때 얻을 수 있는 점수 중 최대 점수를 출력하시오.

입력

첫째 줄에 문자열의 길이 정수 이 주어진다.
둘째 줄에 문자열 가 주어진다.

• 
  
• 는 알파벳 소문자로만 구성되어 있다.

출력

문자열을 나눠서 얻을 수 있는 최대 점수를 출력한다.