시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB69825521635.702%

문제

오세준이 살고 있는 도시에는 사람들의 과속문제가 심각하다. 따라서, 이 도시의 경찰서장은 동호도로에서 과속하는 사람들을 적발하라는 지시를 오세준에게 내렸다. 오세준은 두 개의 속도 측정계를 가져와서 동호도로의 시작과 끝에 설치했다. 그리고, 각각의 차가 동호도로에 들어가는 시간과, 나오는 시간을 기록했다. 오세준은 동호도로에서 과속하는 사람을 쉽게 골라낼 수 있었고, 그 사람들이 벌금을 내게 만들었다.

오세준은 다람쥐를 이용한 불법 도박에 연루된 사실이 밝혀지자 경찰서에서 잘리게 되었다. 오세준은 이대로 잘릴 수 없다고 생각해서, 들어가는 시간과 나오는 시간을 기록한 데이터를 모두 섞어버렸다. 따라서, 정문이는 어떤 들어가는 시간이 어떤 나오는 시간과 일치되는지 알아낼 수 없었다.

정문이는 올해 경찰서의 예산문제 때문에, 벌금을 어떻게든 징수해야 한다. 정문이는 들어간 시간의 정보와 나오는 시간의 정보를 가지고 있다. 그리고, 과속 기준 시간을 가지고 있다. 만약 어떤 차가, 과속 기준 시간보다 작은 시간으로 도로를 통과하면 과속으로 처리한다. (어떤 차가 아무리 빨리 달리더라도 항상 도로를 통과하는 데는 적어도 1초가 걸린다.)

정문이는 들어가는 시간이 나오는 시간보다 이르도록 두 시간을 연관시켜야 한다. 그리고 모든 시간은 단 한 번만 사용할 수 있다. 정문이가 모든 시간을 연관시키고 난 후에는, 각각의 차의 과속 여부를 판별해서 벌금을 징수할 수 있다.

만약 어떤 차가 과속을 했고, 도로를 통과하는데 걸린 시간이 S이고, 과속 기준 시간이 T이면, 정문이는 (T-S)의 제곱만큼 벌금을 징수할 수 있다. (최대 F원, F원을 넘으면 F원의 벌금이 징수된다.) 만약, 과속을 하지 않았으면, 벌금은 징수되지 않는다.

정문이가 징수할 수 있는 벌금의 최솟값과 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 차가 총 몇 대 있는지 주어진다. 이 값을 N이라고 하고, 50보다 작거나 같은 자연수이다. 둘째 줄에는 차가 동호도로에 들어가는 시간이 주어진다. 총 N개의 수가 공백 한 칸을 사이에 두고 주어진다. 셋째 줄에는 차가 동호도로에서 나오는 시간이 주어진다. 마찬가지로 N개의 수가 공백 한 칸을 사이에 두고 주어지며, 모든 시간은 0보다 크거나 같고, 1,000보다 작거나 같은 자연수이다. 넷째 줄에는 과속 기준 시간 T가 주어지고, 다섯째 줄에는 벌금의 최댓값 F가 주어진다. T는 1보다 크거나 같고 1,000보다 작거나 같은 자연수이고, F는 0보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수 2개를 공백 한 칸으로 구분하여 출력한다. 첫 번째 수는 정문이가 징수할 수 있는 벌금의 최솟값이고, 두 번째 수는 최댓값이다. 만약, 주어진 입력으로 N개의 정보를 만들 수 없으면 -1을 출력한다.

예제 입력 1

2
1 2
4 5
3
100

예제 출력 1

0 1

예제 입력 2

2
2 1
60 40
100
100

예제 출력 2

200 200

예제 입력 3

5
1000 584 390 392 109
987 724 814 597 422
1
30

예제 출력 3

-1

예제 입력 4

3
1 2 3
4 5 6
7
42

예제 출력 4

48 56

출처