Novinski는 알고리즘 문제를 풀다 배가 고파서 편의점에 가기 위해 집을 나섰다. 그런데 편의점 맞은 편 횡단보도를 건너다 트럭에 치였고 덕분에 이세계(異世界) 생활을 시작하게 되었다. 이세계를 탐험 하던 중 그는 깊은 숲 속에서 야생의 알고리즘 문제들을 N개 만났고, 집으로 돌아가기 위해 알고리즘 문제와의 대결에서 무사히 살아남아야 한다.
그는 알고리즘 문제와의 대결 전, 상점에서 본인의 PS력(力)를 올려줄 수 있는 알약을 사서 복용한다. 알약을 먹으면 Novinski의 PS력은 K가 된다. PS력은 음수가 될 수 없다. 알고리즘 문제를 풀 때, 알고리즘 문제의 난이도 보다 Novinski의 현재 PS력이 높다면 Novinski는 무사히 문제를 풀 수 있다. 그러나, Novkinski의 현재 PS력이 알고리즘 문제의 난이도보다 같거나 낮다면 그는 두 가지 행동을 할 수 있다.
- 저주를 받고 해당 문제를 영원히 삭제한다. 저주는 앞으로 10개의 문제를 만날 때까지 지속되며, Novinski의 PS력을 10 감소시킨다. 저주는 중첩해서 받을 수 없고, 저주에 걸린 상태에서 죽으면 저주에 의해 감소된 PS력은 회복되지 않는다.
- 해당 문제와의 대결에서 패배하고, 죽는다. 그리고 사망귀환 하여 첫 번째 문제부터 다시 시작한다. 그런데 다시 이 문제를 만나게되면, 본인의 PS력과 관계없이 이 문제를 풀 수 있게 된다.
그런데, 그는 총 M번까지 사망귀환 할 수 있다. 그보다 많이 시도할 경우, 패닉 상태에 빠져 다시는 알고리즘 문제를 풀 수 없게 된다.
최대 사망귀환 횟수 M과 (M은 100,000이하의 자연수) 야생의 알고리즘 문제 N개의 (N은 1,000,000 이하의 자연수) 난이도 정보를 담은 배열이 주어진다. 알고리즘 문제의 난이도는 10000 이하의 자연수이다. Novinski가 모든 문제를 해결할 수 있는 최소의 PS력 K를 구하시오 (제한시간 1초).
취미로 알고리즘 문제 만드는 사람