연례 전국 고양이의 날(NCD) 기념행사 동안 고양이들의 멸종을 성공적으로 막아낸 고양이 켓(Ket)은 이제 식인 고양이 왕국으로부터 굶주림에 대한 불만을 접수했습니다. 이에 따라 켓은 고양이들이 다시 식인 행위에 의존하지 않도록 음식을 배달하는 임무를 맡게 되었습니다.
이 고양이 왕국은 서쪽에서 동쪽으로 뻗어 있는 매우 긴 도로로 모델링할 수 있습니다. 도로의 서쪽 끝에는 푸드 뱅크가 있습니다. 푸드 뱅크 동쪽에는 $1$부터 $n$까지 번호가 매겨진 $n$개의 고양이 집이 있습니다. $n$은 짝수임이 보장됩니다. 첫 번째 집은 푸드 뱅크에서 동쪽으로 $d[1]$ 킬로미터 떨어져 있습니다. $i \ge 2$인 경우, $i$번째 집은 $(i - 1)$번째 집에서 동쪽으로 $d[i]$ 킬로미터 떨어져 있습니다.
켓은 음식을 배달하기 위해 배달 트럭을 운전합니다. 트럭은 푸드 뱅크에서 출발하며 처음에 $x$만큼의 연료를 가지고 있습니다. 연료 $1$단위로 켓은 트럭을 도로 위에서 $1$킬로미터 운전할 수 있습니다.
$i$번째 집에는 트럭이 사용할 수 있는 $f[i]$만큼의 연료가 있습니다. 트럭은 무제한의 연료 저장 공간을 가지고 있으며 연료가 떨어졌을 때만 멈춥니다. 트럭은 출발 후 푸드 뱅크로 돌아올 필요가 없습니다.
또한, 켓에게는 마법 지팡이가 있습니다. 지팡이를 한 번 휘두를 때마다 $i$번째 집과 $(n - i + 1)$번째 집에 저장된 연료의 양을 서로 바꿀 수 있습니다. 이 교환은 두 집에 있는 연료가 아직 사용되지 않았을 때만 가능합니다. 켓이 임의의 횟수만큼 교환을 사용하여 도달할 수 있는 가장 먼 집의 번호 $D$를 찾도록 도와주세요. 또한, 집 $D$에 도달하기 위해 필요한 최소 교환 횟수 $S$를 찾도록 도와주세요.
입력
프로그램은 표준 입력에서 읽어야 합니다.
첫 번째 줄에는 두 개의 공백으로 구분된 정수 $n$과 $x$가 주어집니다.
두 번째 줄에는 $n$개의 공백으로 구분된 정수 $d[1], d[2], \dots, d[n]$이 주어집니다.
세 번째 줄에는 $n$개의 공백으로 구분된 정수 $f[1], f[2], \dots, f[n]$이 주어집니다.
출력
프로그램은 표준 출력으로 출력해야 합니다.
한 줄에 두 개의 공백으로 구분된 정수를 출력하십시오. 첫 번째 정수는 켓이 도달할 수 있는 가장 먼 집의 번호 $D$여야 하며, 이어서 집 $D$에 도달하기 위해 필요한 최소 교환 횟수 $S$를 출력하십시오.
제한
모든 테스트 케이스에 대해 입력은 다음 범위를 만족합니다:
- $2 \le n \le 500\,000$
- $n$은 짝수입니다.
- 모든 $1 \le i \le n$에 대하여 $1 \le d[i] \le 10^9$
- 모든 $1 \le i \le n$에 대하여 $1 \le f[i] \le 10^9$
- $d[1] \le x \le 10^9$
프로그램은 다음 제한을 만족하는 입력 인스턴스에서 테스트됩니다:
| 서브태스크 | 점수 | 추가 제한 | ||
|---|---|---|---|---|
| 0 | 0 | 예제 테스트 케이스 | ||
| 1 | 7 | $ | f[i] - f[n - i + 1] | = k$ (상수 $k$) |
| 2 | 12 | $n \le 40$ | ||
| 3 | 14 | $f$는 비감소함 ($1 \le i \le n - 1$인 모든 $i$에 대해 $f[i] \le f[i + 1]$) | ||
| 4 | 19 | $D \le \frac{n}{2}$ | ||
| 5 | 21 | $n \le 5000$ | ||
| 6 | 27 | 추가 제한 없음 |
참고
숫자 $x$의 절댓값 $|x|$는 수직선 위에서 $0$과 $x$ 사이의 거리에 해당하는 음수가 아닌 숫자입니다. 예를 들어, $|5| = 5$이고 $|-5| = 5$입니다.
예제
입력 1
6 1 1 1 3 1 1 6 1 1 1 4 3 2
출력 1
5 1
참고
푸드 뱅크 동쪽에 $n = 6$개의 집이 있습니다. 켓의 트럭은 $x = 1$의 연료로 시작하여 1번 집으로 이동합니다. 그 후 1번 집에서 연료를 보충하고 2번 집으로 이동합니다. 이 시점에서 켓이 마법 지팡이를 사용하여 2번 집과 5번 집의 연료량을 교환하는 것이 최적이며, 이를 통해 3만큼의 연료를 보충하여 3번 집까지 도달할 수 있습니다. 그 후, 다음 두 집으로 이동하기 전에 1만큼의 연료를 보충할 수 있으며, 4번 집과 5번 집에서 (앞선 교환으로 인해) 각각 4와 1만큼의 연료를 보충합니다.
그러면 4만큼의 연료가 남게 되는데, 6번 집까지는 6만큼의 연료가 필요하므로 이동할 수 없습니다. 켓은 6번 집에 도달하기 전에 연료가 떨어지므로 5번 집까지만 이동할 수 있습니다. 또한, 마법 지팡이를 사용하여 한 번의 교환을 수행해야 했습니다. 따라서 $D = 5$이고 $S = 1$입니다.
입력 2
6 5 3 8 3 1 4 1 2 7 1 6 2 7
출력 2
6 1
입력 3
6 2 2 24 25 40 5 11 4 12 14 16 20 30
출력 3
3 2
입력 4
6 10 3 6 3 7 8 6 4 3 1 7 1 6
출력 4
5 1
고양이 왕국 도로 모델