시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
0.5 초 256 MB 1 1 (100%) 1
문제
Georg의 새 MP3 플레이어에는 많은 재밌는 기능들이 있는데 그중 하나가 버튼 잠금이다. $T$초 동안 아무것도 하지 않으면 모든 버튼이 잠기게 된다. 버튼 잠금 상태에서 모든 버튼은 원래 기능대로 작동하지 않지만 아무 버튼이나 눌렀을 때 버튼 잠금은 해제된다. 예를 들어 $T = 5$ 이고 현재 MP3 플레이어가 잠금인 상태라고 하자. Georg가 $A$ 버튼을 누르고 3초를 기다렸다가 $B$ 버튼을 누르고 5초를 기다렸다가 $C$ 버튼을 누르고 6초를 기다렸다가 $D$ 버튼을 눌렀다고 하자. 이런 경우 $B$와 $C$ 버튼만 원래의 기능대로 작동하게 된다. 이때 $C$와 $D$ 버튼을 누르는 사이에 버튼 잠금이 일어났다는 점을 알 수 있다. MP3 플레이어의 음량은 + 와 - 버튼으로 조절되고, 이들은 한 단위씩 음량을 증가시키거나 감소시킨다. 음량은 $0$과 $V_{max}$ 사이의 정수이다. 음량이 $V_{max}$인 상태에서 + 버튼을 누르거나 0인 상태에서 - 버튼을 누르면 음량은 변하지 않는다. Georg는 $T$의 값을 알지 못한다. 그는 실험을 통해 이를 알아보려고 한다. 잠금상태에서 시작하여 그는 + 버튼과 - 버튼을 $N$번 눌렀다. 실험이 끝나고 그는 MP3 플레이어의 화면에서 마지막 상태의 음량을 확인했다. 안타깝게도 그는 실험 전에 음량이 얼마였는지 기억하지 못한다. 이 알 수 없는 초기의 음량을 $V_1$이라 하고 마지막 상태의 음량을 $V_2$라고 하자. $V_2$와 Georg가 버튼을 누른 기록(각 시행에서 + 버튼을 눌렀는지, - 버튼을 눌렀는지와 실험이 시작하고 몇 초 뒤에 해당 시행이 일어났는지가 주어진다)이 주어졌을 때 실험의 결과와 모순되지 않는 $T$값 중 가능한 가장 큰 정수를 구하여라.
입력
첫째 줄에 띄어쓰기로 구분된 $3$개의 정수 $N, V_{max}와 V_2(0 \le V_2 \le V_{max})$가 주어진다. 다음 $N$개의 줄에는 어떤 버튼을 언제 눌렀는지에 대한 정보가 주어진다. 각 줄의 처음에는 문자 + 혹은 -가 주어지며 이는 +나 - 버튼을 눌렀음을 의미하고 다음에는 정수 $C_i(0 \le C_i \le 2\times10^9)$가 주어지는데 이는 실험이 시작하고 $C_i$초 뒤에 이 버튼을 눌렀음을 의미한다. 각 시행은 시간순서로 정렬되어있고 모든 시행시간은 서로 다르다고 가정해도 된다, 즉 모든 $1 \le i \le N$ 인 $i$에 대해 $C_i < C_i+1$ 를 만족시킨다.
출력
$T$가 무한하게 커질 수 있다면 문자열 "infinity"(따옴표는 출력하지 않는다) 한 줄을 출력하라. 아니라면 두 정수 $T$와 $V_1$사이에 공백을 한 칸 두고 한 줄에 출력하라. 이 값들은 잠금 시간 $T$초, 시작 음량 $V_1$으로 주어진 실험을 반복했을 때 최종 음량이 $V_2$가 되도록 하는 값이어야 한다. 여러 개의 해가 존재할 경우 $T$가 가장 큰 경우를, 여전히 여러 해가 존재한다면 그중 $V_1$이 가장 큰 경우를 출력하라. ($T = 0, V_1 = V_2$ 인 경우로 적어도 하나의 해가 존재한다는 점을 알 수 있다.)
힌트
#### 제약조건 $2 \le N \le 100,000$ 이고 $2 \le V_{max} \le 5,000$ 이다.
40점에 해당하는 서브태스크에서 $N \le 4,000$ 이다.
나머지 중 30점에 해당하는 서브태스크에서 $N*V_{max} \le 400,000$ 이다. 시간 제한은 0.5초, 메모리 제한은 256MB이다. #### 예제 입력 1 ``` 6 4 3 - 0 + 8 + 9 + 13 - 19 - 24 ``` #### 예제 출력 1 ``` 5 4 ``` $T = 5$에 대해 위 실험은 잠금해제, 잠금해제, +, +, 잠금해제, - 와 같이 수행되게 된다. $V_1 = 2, 3, 4$ 인 경우 $V_2 = 3$ 을 얻을 수 있고 그중 가장 큰 값이 출력되었다. $T \ge 6$ 인 경우 마지막 두 시행이 모두 실제 버튼 입력으로 실행될 것이므로 $V_2 = 3$ 이 되도록 할 수 없다. #### 예제 입력 2 ``` 3 10 10 + 1 + 2 + 47 ``` #### 예제 출력 2 ``` infinity ``` $V_1 = 10$ 이면 어떠한 $T$에 대해서도 $V_2 = 10$ 이 나올 것이다.