꽤 오래된 옛날에 스페인 아이들은 부활절에 폭죽을 사용하는 것이 허락되었다. 자그마한 박스를 날려버리는게 쉬워서 우체통이 그들의 주요 목표물이었다.

자 , 우체통 만드는 회사는 새로 만던 우체통의 견본이 화약에 폭발하지 않고 얼마나 많이 견디는 지에 관심이 있어서 , 그들 도와 주도록 당신을 채용했다.

동일한 메일 박스 k ( 1 <= k <= 10 ) 개, 최대 테스트할 폭죽의 수 m ( 1 <= m <= 100 ) 이 주어질 때 이 메일박스가 폭죽에 얼마나 견딜 수 있는가를 알아내기 위해서 필요한 최소 폭죽 수를 구하는 것이 문제이다.

만약 한개의 메일박스를 주고 최대 테스트할 최대 폭죽수가 m 이라면 1 개의 폭죽으로 테스트를 시작하고 , 그리고 2 개 ... . 최악의 경우 m 개의 폭죽으로도 폭발하지 않는다면 필요한 폭죽은 1+2+...+m = m*(m+1)/2 개의 폭죽이 필요하다.

m = 100 이라면 5000 개 이상의 폭죽이 필요할 것이다.

다음과 같은 가정을 하자.

1. 메일박스가 x 개의 폭죽을 견딘다면 x - 1 개의 폭죽도 견딜 수 있다.
2. 폭발이 있은 후 , 두 상태중 하나다. 완전히 파괴되던지 아니면 다음 테스트를 위해서 재 사용할 수 있던지.

메일 박스가 m 개의 폭죽의 부하를 견딜 수 있다면 물론 제조업자는 그 답에 만족할 것이다. 그러나 그렇지 않다면 그는 메일박스가 견딜 수 있는 최대개수의 폭죽을 계속 찾을 것이다.

입력

출력

입출력 예

입력

4
1 10
1 100
3 73
5 100

출력

55
5050
382
495

출처:Svenskt Masterskap i Programmering/Norgesmesterskapet 2002