| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 316 | 131 | 109 | 43.600% |
엘나스 산맥에는 설원에 세워진 마을 엘나스와 하늘섬 오르비스를 이어주는 거대한 탑인 오르비스 탑이 있다.
오르비스 탑은 지상으로 $M$개의 층이 있고, 층마다 정확히 같은 레벨의 몬스터만 서식한다. $i$층에는 레벨이 $l_i$인 몬스터가 서식하고 있고, 서로 다른 층에는 같은 레벨을 가진 몬스터가 서식하지 않는다.
엘나스 마을에는 $N$명의 용사들이 살고 있다. $i$번째 용사는 레벨이 $h_i$이고, 용사들은 $K$일 동안 오르비스 탑에서 사냥해 레벨업을 하려고 한다.
각 용사는 200ドル$레벨이 되거나 $K$일이 전부 지나기 전까지 매일 1ドル$층에서 출발하여 자신의 레벨 이하의 몬스터 중 가장 높은 레벨의 몬스터가 있는 층으로 이동한 후, 그 층에서 사냥해 레벨을 1ドル$만큼 올리고, 즉시 마을 귀환 주문서를 통해 마을로 귀환한다. 200ドル$레벨이 된 용사는 더 이상 오르비스 탑에서 사냥하지 않는다.
그러나 $M$층이나 되는 탑을 오르는 일은 여간 어려운 일이 아니다. 용사들은 이동 시간이 너무 오래 걸리는 것에 불만을 호소했고, 오르비스 탑의 연구자 허클은 한 쌍의 마법석을 적절한 층에 배치해 이동 시간 합계를 최대한 단축해 주기로 했다.
층 하나를 오르거나 내려갈 때는 1ドル$만큼의 시간이 걸리는데, 마법석이 있는 층에 위치한 용사는 다른 마법석이 있는 층까지 즉시 이동할 수 있고, 여기에는 시간이 소모되지 않는다.
각 용사의 레벨과 탑에 서식하는 몬스터의 정보를 조사해 온 허클은 어느 층에 마법석을 배치해야 할지 알아냈고, 용사들이 첫 사냥을 시작하기 전, 한 쌍의 마법석을 서로 다른 두 층에 배치하였다. 이 두 마법석은 $K$일이 지나 모든 용사가 사냥을 멈출 때까지 그 위치에 고정되어 있을 것이다.
허클이 알아낸 용사들의 이동 시간 합계를 최소화하는 두 마법석의 적절한 위치와, 그때의 모든 용사가 $K$일 동안 마법석으로 절약한 이동 시간의 합계를 구해 보자.
첫 번째 줄에 용사의 수 $N,ドル 탑의 층수 $M,ドル 용사들이 사냥하는 기간 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 626,円 852;$ 2ドル \le M \le 200;$ 1ドル \le K \le 200)$
두 번째 줄에 각 용사의 초기 레벨을 나타내는 $N$개의 정수 $h_1, h_2, \cdots, h_N$가 공백으로 구분되어 주어진다. $(1 \le h_i \le 200)$
세 번째 줄에 각 층에 서식하는 몬스터의 레벨을 나타내는 서로 다른 $M$개의 정수 $l_1, l_2, \cdots, l_M$이 공백으로 구분되어 주어진다. $(1 \le l_i \le 200)$
가장 낮은 레벨의 몬스터는 가장 낮은 레벨의 용사보다 레벨이 낮거나 같다. $(\min(l_i) \le \min(h_j))$
첫 번째 줄에 두 마법석이 있을 곳으로 적절한 층 $x,ドル $y$를 공백으로 구분하여 출력한다. $(1 \le x, y \le M;$ $x \neq y)$ 적절한 위치가 여럿이 있다면 그중 아무거나 출력한다.
두 번째 줄에 그때의 모든 용사가 마법석으로 절약한 이동 시간의 합계를 출력한다.
마법석으로 절약한 시간은, 마법석을 사용하지 않았을 때 걸리는 이동 시간에서 마법석을 사용했을 때 걸리는 이동 시간을 뺀 것이다.
3 4 10 1 22 199 1 23 30 76
1 2 10
3 6 2 12 12 10 1 2 13 11 4 10
1 4 14
2 8 3 1 2 1 10 20 30 40 50 60 70
8 4 0
용사의 수 $N$의 제한 626ドル,852円$는 2011년 달성한 메이플스토리의 최고 동시 접속자 수이다.