결투

두 병사의 결투

토마스는 전쟁 게임의 열렬한 팬이다. 현재 그가 가장 좋아하는 게임은 다수의 결투이다. 이 게임에서는 두 플레이어가 전투를 벌인다. 각 전투는 여러 결투로 이루어진다.

토마스에게는 $n$명의 병사가 있으며, 각 병사의 힘은 $a_i$로 나타낸다. 토마스의 상대에게도 $n$명의 병사가 있으며, 각 병사의 힘은 $b_i$로 나타낸다.

결투에서는 토마스의 $i$번째 병사가 상대의 $i$번째 병사와 싸운다. $a_i > b_i$이면 토마스가 결투에서 이기고, $a_i = b_i$이면 무승부이며, $a_i < b_i$이면 상대가 이긴다. 결투는 오름차순으로 진행된다. 먼저 $a_1$와 $b_1$가 싸우고, 다음으로 $a_2$와 $b_2$가 싸우며, 이런 식으로 $a_n$와 $b_n$가 싸울 때까지 계속된다.

토마스가 적보다 더 많은 결투에서 이기면 전투에서 승리한다.

토마스는 최근 이 게임의 확장팩을 구매했으며, 그 안에는 초강력 물약 하나가 들어 있었다. 토마스가 초강력 물약을 사용하면 이후 $m$번의 결투 동안 그의 병사들의 힘이 $k$만큼 강해진다.

토마스는 초강력 물약을 언제 사용해야 할지 확신하지 못한다. 사용할 최적의 시점을 선택한다면 토마스는 전투에서 승리할 수 있을까?

채점

그룹 | 점수 | 제한

1 | 50 | $1 \le m \le n \le 1\,000$, $1 \le k, a_i \le 100$

2 | 100 | 추가 제한 없음

첫째 줄에는 세 정수 $n,m,k$가 주어지며, $1 \le m \le n \le 10^5$, $1 \le k \le 10^7$이다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \dotsc, a_n$가 주어지며, $1 \le a_i \le 10^7$이다. 셋째 줄에는 $n$개의 정수 $b_1, b_2, \dotsc, b_n$가 주어지며, $1 \le b_i \le 10^7$이다.

토마스가 전투에서 승리할 수 있다면, 초강력 물약을 사용하여 전투에서 승리할 수 있는 가장 이른 시점을 출력한다. 토마스가 전투에서 승리할 수 없다면 Neibb을 출력한다.