달리기

Bessie는 길이 $K$ ($1\le K\le 10^9$)미터의 경주를 달린다. 그녀는 속도 0미터/초로 달리기 시작한다. 어떤 1초 동안 그녀는 속도를 1미터/초만큼 높이거나, 그대로 두거나, 1미터/초만큼 낮출 수 있다. 예를 들어 첫 1초에 그녀는 속도를 1미터/초로 높여 1미터를 달리거나, 속도를 0미터/초로 유지하며 0미터를 달릴 수 있다. Bessie의 속도는 결코 0 아래로 떨어질 수 없다.

Bessie는 항상 결승선을 향해 달리고, 정수 초 후에 달리기를 마치려고 한다(그 정수 시각에 결승선에 도달하거나 결승선을 지나쳐야 한다). 게다가 결승선에서 너무 빠르게 달리는 것을 원하지 않는다. Bessie가 $K$미터를 다 달린 그 순간의 속도가 $X$ ($1 \leq X \leq 10^5$)미터/초 이하여야 한다. Bessie는 $N$ ($1 \leq N \leq 1000$)개의 서로 다른 $X$ 값에 대해 경주를 얼마나 빨리 마칠 수 있는지 알고 싶어 한다.

첫 번째 줄에 두 정수 $K$와 $N$이 주어진다.

다음 $N$개의 줄에 각각 정수 $X$가 하나씩 주어진다.

$N$개의 줄을 출력한다. 각 줄에는 Bessie가 속도 $X$ 이하로 달리기를 마치면서 $K$미터를 달리는 데 필요한 최소 시간을 나타내는 정수 하나를 출력한다.

$X = 1$일 때 최적의 방법은 다음과 같다.

1. 속도를 1m/s로 높이고 1미터 이동
2. 속도를 2m/s로 높이고 2미터 이동, 합계 3미터
3. 속도를 2m/s로 유지, 합계 5미터 이동
4. 속도를 2m/s로 유지, 합계 7미터 이동
5. 속도를 2m/s로 유지, 합계 9미터 이동
6. 속도를 1m/s로 낮추고 합계 10미터 이동

$X = 3$일 때 최적의 방법은 다음과 같다.

1. 속도를 1m/s로 높이고 1미터 이동
2. 속도를 2m/s로 높이고 합계 3미터 이동
3. 속도를 3m/s로 높이고 합계 6미터 이동
4. 속도를 3m/s로 유지, 합계 9미터 이동
5. 속도를 3m/s로 유지, 합계 12미터 이동

다음은 $X = 3$일 때 허용되지 않는 방법이다.

1. 속도를 1m/s로 높이고 1미터 이동
2. 속도를 2m/s로 높이고 합계 3미터 이동
3. 속도를 3m/s로 높이고 합계 6미터 이동
4. 속도를 4m/s로 높이고 합계 10미터 이동

Bessie가 10미터를 다 달린 그 순간의 속도가 4m/s이기 때문이다.