그냥 퀴즈일 뿐

TV 퀴즈 프로그램에서 참가자는 주제를 하나 고르고, 정해진 시간 동안 그 주제에 관한 문제를 받는다. 정답을 맞힐 때마다 1점을 얻는다. 시간이 다 되면 참가자는 더 말할 수 없다.

테레사는 나올 수 있는 문제와 그 정답을 모두 아는 아주 좁은 주제를 찾아냈다. 경쟁이 치열해서, 사회자가 문제를 다 읽기 전에 답을 말하기로 했다. 사회자는 $n$개의 문제 중 하나를 매번 균등한 확률로 고르고, 같은 문제가 여러 번 나올 수도 있다. 문제를 읽는 속도는 1초에 한 단어다.

테레사는 단어와 단어 사이에서 사회자의 말을 끊을 수 있고, 첫 단어를 듣기 전에 끊을 수도 있다. 단어 중간에 끊는 것은 너무 무례하므로 하지 않는다. 답을 말하는 데에도 1초가 걸리고, 답이 끝나면 사회자는 곧바로 다음 문제를 읽기 시작한다. 물론 테레사는 그 문제도 도중에 끊을 수 있다.

테레사가 최적으로 행동할 때 얻는 점수의 기댓값을 구하라.

첫 번째 예제에서는 단어 하나만 들으면 정답이 정해지므로, 한 단어를 듣고 바로 답하는 것이 최적이다. 테레사는 4초 동안 두 문제를 맞힌다. 두 번째 예제에서는 첫 단어가 What이면 문제가 끝날 때까지 기다리는 데 시간이 너무 많이 든다. 그래서 테레사는 Now!를 네 번 외치고, 그중 3분의 1을 맞힐 것으로 기대한다.

첫 줄에 퀴즈 시간 $t$와 문제의 개수 $n$이 주어진다. ($1 \le t \le 100$, $1 \le n \le 100\,000$)

다음 $n$개의 줄에는 각각 문제 하나와 그 정답이 주어진다. 한 줄은 공백으로 구분된 단어들이고, 마지막 단어가 정답이며 그 앞의 단어들이 문제다. 문제의 마지막 단어는 물음표로 끝나고, 문제의 나머지 단어에는 물음표가 없다. 정답에는 물음표가 들어갈 수도 있다.

각 단어는 ASCII 코드 33(!)부터 126(~)까지의 문자로만 이루어진다. 문장 부호도 단어의 일부이고, 대소문자가 다른 단어는 서로 다른 단어다. 어떤 문제의 단어 나열도 다른 문제의 단어 나열의 접두사가 되지 않는다.

한 줄에 등장하는 모든 단어의 문자 수를 전부 더한 값은 $100\,000$ 이하다.

최적 전략으로 얻는 점수의 기댓값을 소수점 아래 정확히 10자리로 반올림해 한 줄에 출력한다.