Informatica Online Judge

  BamGong #3 [2242 / 08C2]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[35th 임유진]
Writer ID : [gs17100]

Background

경곽은 훌륭한 교육과정과 친구들, 그리고 매우매우매우 많은 수행평가를 제공한다.

경곽인들은 이 많은 수행평가를 모두 해내기 위해 "밤공"이라는 문화를 만들어 냈다.

밤공이란, 자습시간이 종료된 후 기숙사에서 몰래 공부를 하는 것을 말한다.

밤공을 하면 많이 피곤해지지만, 그럼에도 불구하고 경곽인들은 밤공을 한다.

유진이는 매우 많은 수행평가를 마주하게 되었다.

유진이는 이 많은 수행평가를 모두 해결하고자 한다.

유진이가 공부를 할 수 있는 방법은 자습시간과 밤공, 두 가지이다.

자습시간은 매일 저녁 a시간씩 주어진다.

그리고 기숙사에 들어간 후에는 밤공을 한다.

소등을 하고 b시간이 지나면 아침 점호를 나가야 하기 때문에 하루동안 잠자는 시간과 밤공하는 시간의 합은 b시간이다.

유진이는 정수를 좋아하기 때문에 밤공을 1시간 단위로 끊어서 한다.

즉, 1시간 30분동안 밤공을 하는 것은 불가능하고, 1시간 또는 2시간 동안 밤공을 해야한다는 것이다.

유진이가 해결해야 하는 수행은 N가지가 있다.

i번째 수행평가를 하는데는 k_i시간이 걸리고, t_i일 1교시까지 제출을 해야한다.

즉, i번째 수행평가를 최대한 미루면 전날 밤공을 하게 된다.

밤공을 하루에 몰아서 하면 다음 날 헤롱헤롱해지기 때문에, 유진이는 밤공을 적고 고르게 하고 싶다.

구체적으로는, 밤공 하는 양의 제곱의 합을 최소로 하고자 한다.

유진이가 밤공을 현명하게 할 때, 밤공 양의 제곱의 합의 최솟값을 구하여라.

Input

입력파일의 첫째 줄에는 수행평가의 수 N, t_i의 최댓값 T가 주어진다.(1<=N<=2*10^6, 1<=T<=2*10^6)

두번째 줄에는 자습시간 a, 하루에 할 수 있는 밤공의 양 b이 주어진다.(1<=a<=10^6, 1<=b<=10^6)

세번째 줄부터 N개의 줄에는 i번째 수행평가를 하는데 걸리는 시간과 제출일 k_i와 t_i가 주어진다.(1<=i<=N, 1<=k_i<=10^9, 1<=t_i<=T)

서브태스크
#1: N<=2,000,000

Output

밤공양의 제곱의 합의 최솟값을 출력한다.

모든 수행평가를 끝내는 것이 불가능하다면, "Drop Out"을 출력한다. (따옴표 제외)

("Drop Out"의 뜻은 "자퇴"이다)

IO Example

입력1
4 15
5 8
4 3
9 3
37 10
3 9

출력1
10

입력2
2 100
2 3
1 1
50 1

출력2
Drop Out

1번 예제 설명
1 2 3 3 4 3 3 3 3
1 2 3 3 4 3 3 3 3
1 2 3 3 4 3 3 3 3
1 2 3 3 3 3 3 3 3
2 2 3 3 3 3 3 3 3

2 2 3 3 3 3 3
2

1일째에는 자습 2시간동안 1번 수행평가를 하고, 자습 3시간과 밤공 2시간 동안 2번 수행평가를 한다.
2일째에는 자습 5시간과 밤공 1시간 동안 2번 수행평가를 한다.
3일째와 4일째에는 자습 5시간과 밤공 1시간 동안 동안 3번 수행평가를 한다.
4일째에는 자습 5시간과 밤공 1시간 동안 3번 수행평가를 한다.
5일째에는 자습 3시간동안 4번 수행평가를 하고, 자습 2시간과 밤공 1시간 동안 3번 수행평가를 한다.
6일째와 7일째에는 자습 5시간과 밤공 1시간 동안 3번 수행평가를 한다.
8일째와 9일째에는 자습 5시간 동안 3번 수행평가를 한다.
10일째부터는 마음껏 잔다.
밤공양의 제곱의 합은 4+1+1+1+1+1+1=10이다.

2번 예제 설명
1일째 등교 전까지 수행평가를 하는 것은 불가능하다. 따라서 수행평가를 끝내는 것이 불가능하다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]