화질 - 자동 (480p)
시간 제한2초메모리 제한512 MB
시청자 500명의 시청 구간과 화질별 만족도가 주어질 때, 공유 대역폭 한도 안에서 시간에 따른 화질을 정해 전체 만족도의 합이 최대가 되도록 한다.
문제
상민이는 하루 일과를 마치고 저녁에 너튜브를 보는 것이 삶의 유일한 낙이다. 그러나 저녁 시간에는 다른 사람들도 너튜브를 많이 보기 때문에, 너튜브 서버의 네트워크 대역폭이 부족한 날에는 영상이 자주 끊겼다. 이를 참을 수 없던 상민이는 문제를 해결하려고 너튜브에 입사해 다음과 같은 알고리즘을 만들었다.
- 너튜브에서는 6종류의 화질 옵션을 제공한다.
- 화질 옵션마다 재생할 때 차지하는 일정량의 네트워크 대역폭이 있다.
- 모든 시청자에게서 화질 옵션마다 느끼는 만족도를 수집한다.
- 매 분마다 시청 중인 시청자들의 만족도의 합이 최대가 되도록 시청자들의 화질 옵션을 조정한다. 이때 시청자들이 사용하는 네트워크 대역폭의 합이 너튜브 서버의 네트워크 대역폭을 초과하지 않도록 조정한다.
화질 옵션은 화질이 높은 순서대로 8K, 4K, FHD, HD, 480p, 240p가 있다. 즉, 가장 높은 화질 옵션은 8K이고 가장 낮은 화질 옵션은 240p다. 높은 화질 옵션일수록 네트워크 대역폭을 많이 차지하고, 낮은 화질 옵션일수록 적게 차지한다. 서버의 네트워크 대역폭이 부족해 어떤 시청자가 어떤 화질 옵션으로도 시청할 수 없게 되면, 그 시청자는 네트워크 대역폭을 차지하지 않으며 느끼는 만족도도 0이다.
예를 들어 너튜브 서버의 네트워크 대역폭이 20이고, 시청자 A와 B가 화질 옵션별로 사용하는 대역폭과 수집한 만족도가 아래와 같다고 하자.
<표 1> 화질 옵션별 사용 네트워크 대역폭 예시
<표 2> 시청자의 화질 옵션별 만족도 예시
A는 0분에 시청을 시작해 5분에 끝내고, B는 3분에 시청을 시작해 8분에 끝낸다고 하자.
A는 0분부터 3분까지 8K로 시청할 수 있다. 그러나 3분부터 5분까지는 B와 동시에 8K로 시청하면 서버의 네트워크 대역폭을 초과하므로 시청자의 화질 옵션을 낮춰야 한다.
상민이는 시청자의 만족도를 중요시하기 때문에 모든 시청자의 만족도의 합을 최대화하도록 화질 옵션을 조정한다. 그래서 3분부터 5분까지는 화질 옵션을 낮춰도 만족도가 적게 줄어드는 시청자 B의 화질을 FHD로 낮춘다. 이후 5분에 A의 시청이 끝나면 B의 화질 옵션을 높여 B는 5분부터 8분까지 8K로 시청할 수 있다.
만족도는 분 단위로 계산하므로, A는 32 × 5분 = 160, B는 8 × 2분 + 10 × 3분 = 46으로 총 206의 만족도를 얻는다.
알고리즘을 적용한 뒤 상민이는 시청자들이 변화를 체감할 수 있을지 궁금해졌다. 상민이를 위해 모든 시청자들의 만족도의 합을 계산하자.
입력
첫 번째 줄에 모든 시청자의 수 N과 너튜브 서버의 네트워크 대역폭 W가 주어진다. (1 ≤ N ≤ 500, 1 ≤ W ≤ 5,000)
두 번째 줄에 화질 옵션별로 각 시청자가 사용하는 대역폭 Q8K, Q4K, QFHD, QHD, Q480p, Q240p가 주어진다. (1 ≤ Q240p ≤ Q480p ≤ QHD ≤ QFHD ≤ Q4K ≤ Q8K ≤ W)
세 번째 줄부터 N + 1번째 줄까지 시청 시작 시간 S, 시청 종료 시간 E, 화질 옵션별 만족도 P8K, P4K, PFHD, PHD, P480p, P240p가 주어진다. (1 ≤ S < E ≤ 1,000,000,000, 1 ≤ P240p ≤ P480p ≤ PHD ≤ PFHD ≤ P4K ≤ P8K ≤ 1,000)
출력
상민이의 알고리즘을 적용했을 때 모든 시청자들의 만족도의 합을 출력한다.