23299번 - 화질 - 자동 (480p)

상민이는 하루 일과를 끝내고 저녁에 너튜브를 보는 게 삶의 유일한 낙이다. 그러나 저녁 시간에는 다른 사람들도 너튜브를 많이 보기 때문에 너튜브 서버의 네트워크 대역폭이 부족한 날엔 종종 영상이 끊기곤 했다. 이를 참을 수 없던 상민이는 문제를 해결하기 위해 너튜브에 입사해 다음과 같은 알고리즘을 만들어냈다.

1. 너튜브에서는 6종류의 화질 옵션을 제공한다.
2. 각 화질 옵션마다 재생 시 차지하는 일정량의 네트워크 대역폭이 있다.
3. 모든 시청자에게서 화질 옵션마다 느끼는 만족도를 수집한다.
4. 매 분마다 시청 중인 시청자들의 만족도의 합이 최대가 되도록 시청자들의 화질 옵션을 조정한다. 이때 시청자들이 사용하는 네트워크 대역폭의 합이 너튜브 서버의 네트워크 대역폭을 초과하는 일이 없도록 조정한다.

화질 옵션은 화질이 높은 순서대로 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)

두 번째 줄에 화질 옵션 별로 각 시청자가 사용하는 대역폭 Q_8K, Q_4K, Q_FHD, Q_HD, Q_480p, Q_240p가 주어진다. (1 ≤ Q_240p ≤ Q_480p ≤ Q_HD ≤ Q_FHD ≤ Q_4K ≤ Q_8K ≤ W)

세 번째 줄부터 N + 1번째 줄까지 시청을 시작 시간 S, 시청을 끝내는 시간 E, 화질 옵션별 만족도 P_8K, P_4K, P_FHD, P_HD, P_480p, P_240p가 주어진다. (1 ≤ S < E ≤ 1,000,000,000, 1 ≤ P_240p ≤ P_480p ≤ P_HD ≤ P_FHD ≤ P_4K ≤ P_8K ≤ 1,000)

상민이의 알고리즘을 적용했을 때, 모든 시청자들의 만족도의 합을 출력한다.