iktk   2년 전

문제

당신은 국내 최고의 놀이공원 백준랜드에 놀러 갔습니다. 백준랜드에 입장하기 위해서는 줄을 서야 하는데, 줄을 서는 방식이 특이합니다.

백준랜드 입장 대기줄은 왼쪽부터 오른쪽 순으로 번호가 매겨진 $n$개의 열로 구성됩니다. 이동이 발생할 때마다 사람들은 다음 규칙에 따라 이동합니다.

  • 마지막 열에 있는 사람들부터 순서대로 한 열씩 오른쪽으로 갑니다. 가장 위에 있던 사람이 먼저 출발하며, 가장 아래에 있던 사람이 나중에 출발합니다.
  • 마지막 열($n$번 열)에 있는 사람은 백준랜드에 입장하게 되며, $i$번 열에 있던 사람은 이동 후에 $i+1$번 열로 이동하게 됩니다.

백준랜드의 입장 방식을 그림으로 표현하면 아래와 같습니다.

preview

즉, $5$번과 $6$번 사람이 백준랜드에 입장하게 되고, 나머지 사람들은 계속 대기줄에 남아있게 됩니다.

새로운 사람이 대기줄에 들어오면 그 사람은 $1$번 열의 맨 위로 들어갑니다. 당신은 아직 대기줄에 입장하지 않았습니다. 지금으로부터 정확히 $t$분 후에 첫 이동이 발생하고, 그 이후에도 매 $t$분마다 이동이 발생합니다.

당신은 최대한 빨리 백준랜드에 입장하고 싶습니다. 대기줄에 입장하기 위해 다가오고 있는 사람들도 있으므로, 당신은 대기줄에 입장할 최적의 타이밍을 계산하여야 합니다. 다가오고 있는 사람들은 모두 도착 예정 시각이 다릅니다. 당신은 언제든 원할 때 대기줄에 입장할 수 있습니다.

어떤 사람이 대기줄에 입장하는 시각이 이동이 발생하는 시각과 동일한 경우 그 사람이 대기줄에 입장한 후에 이동이 발생합니다. 당신은 그 사람이 입장하고 나서 이동이 발생하기 전에 입장할 수도 있습니다.

당신은 당신보다 먼저 백준랜드에 입장하는 사람의 수를 최소화하고 싶습니다. 그런 타이밍이 여러 개라면, 다가오고 있는 사람들 중 당신보다 먼저 대기줄에 입장할 사람의 수를 최소화하고자 합니다.

입력

첫 번째 줄에는 세 개의 정수가 포함됩니다. 대기줄에 있는 열의 수, 대기줄로 다가오고 있는 사람의 수와 이동이 발생하는 간격을 나타내는 세 정수 $n$, $m$ 및 $t$ ($1 \le n, t \le 100\,000$; $0 \le m \le 100\,000$)입니다.

두 번째 줄에는 지금 대기줄의 각 열에 서 있는 사람 수를 나타내는 $n$개의 정수 $a_i$($0 \le a_i \le 100\,000$)가 공백으로 구분되어 주어집니다.

세 번째 줄에는 $m$개의 정수 $t_i$가 주어집니다. 대기줄로 다가오고 있는 $i$번째 사람이 대기줄에 도착하기까지의 시간을 분 단위로 나타냅니다. ($1 \le t_i \le 100\,000$; $t_i < t_{i + 1}$)

출력

당신보다 백준랜드에 먼저 입장하는 사람 수의 최솟값과 다가오고 있는 사람들 중 당신보다 대기줄에 먼저 입장할 사람의 수를 공백으로 구분하여 출력합니다.

당신보다 백준랜드에 먼저 입장하는 사람 수를 최소화하는 여러 가지 경우가 있다면 두 번째 숫자를 최소화하십시오.

댓글을 작성하려면 로그인해야 합니다.