승민이는 요즘 PS에 빠져 있다. 인생을 PS에 바쳐버린 승민이는 풀겠다고 마음먹은 문제는 몇 시간이고 며칠이고 붙잡고 있는다. 그러나 그럴 때마다 승민이의 정신은 점점 광기에 물들고 있다. 광기가 너무 많이 쌓이면 문제를 해결하는 데 방해가 되기 때문에, 승민이는 적절한 시기에 효율적으로 휴식을 취하려고 한다.
난이도 인 문제를 시간이 걸려 푸는 동안, 1시간마다 광기가 쌓인다.
문제를 해결했다면, 광기는 만큼 해소된다.
휴식을 취하면, 1시간마다 광기가 만큼 해소된다. 단, 광기는 0 미만으로 떨어지지 않는다.
광기가 너무 많이 쌓이는 걸 방지하기 위해, 승민이는 이하로 광기를 유지하려고 한다. 이 조건을 만족하면서 주어진 문제들을 모두 푸는 최소 시간을 계산하자.
단, 어떤 문제를 푸는 도중에는 휴식할 수 없고, 문제를 다 풀고 다른 문제로 이동해야 한다. 또한, 승민이는 문제를 동시에 해결할 수 없다.
첫 번째 줄에 문제의 개수 ()과 광기의 최대 제한 (은 정수)이 주어진다.
두 번째 줄부터 난이도 (는 정수), 푸는 시간 (는 정수), ()이 공백을 사이에 두고 주어진다.
풀이
난이도 K인 문제를 T시간이 걸려 푸는데 어떤 문제를 먼저풀어야 최단시간으로 풀수있는지를 구하는 문제이므로 그리디, 스케줄링을 먼저 생각해주었다.
한문제를 풀때마다 광기는 만큼 누적되고, 문제를 풀고난 후에 만큼 해소된다.
이를 정리하면 인 경우, 즉 인 경우는 항상 축적된 만큼 해소되므로, 누적되는 광기가 없다.
그리고 인 경우 광기는 누적되게 된다.
그러므로 두번째, 인 경우 누적되는 광기가 을 넘지 않도록 정렬을 해주면 된다.
테케 2번으로 경우의수 따져보니까 가 크고 가 작은 순서대로 정리해준 다음 연산을 해주면 된다. 아직 증명하진 못했다.
