실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
현수에게는 명의 친구가 있습니다. 이 친구들은 밥을 먹는 것 외에 가끔 다른 즐거움을 느끼고 싶어합니다. 친구들을 위한 간식으로, 현수는 개의 탕후루()를 만들었으며, 탕후루에는 의 라벨이 붙어 있습니다. 번째 친구는 에서 까지의 범위에 해당하는 라벨이 붙은 탕후루를 좋아합니다. 또한, 두 친구가 정확히 같은 범위의 탕후루를 좋아하는 경우는 없습니다. 각 친구에는 무게()가 있으며, 이는 범위의 정수입니다.
현수는 자신의 친구를 선택하여 순차적으로 탕후루를 전달하려고 합니다. 안타깝게도, 친구들은 식탐이 굉장히 많습니다. 각 친구는 자신의 차례에서, 자신이 좋아하는 탕후루를 모두 먹게됩니다. 즉, 해당 친구가 좋아하는 탕후루가 이미 다 먹혀버린 상황을 현수는 피하고 싶어합니다. 그렇기 때문에, 각각의 친구가 적어도 한 개의 탕후루를 먹을 수 있는 순서에 대해 가능한 최대 무게()를 계산하게 해주세요.
첫 번째 줄에는 두 개의 정수 과 이 주어집니다 (.).
그 다음 줄에는 , , 그리고 세 개의 정수로 각각의 친구에 대한 정보가 주어집니다.
유효한 순서에 대한 최대 가능 무게를 출력하세요.
2 2 100 1 2 100 1 1
200
이 예제에서, 친구 1이 먼저 탕후루를 먹는다면 친구 2가 먹을 것이 없습니다.
그러나, 친구 2가 먼저 탕후루를 먹는다면 친구 1은 두 번째 탕후루만 먹으면 만족합니다.
출처: USACO 2019 December Contest, Platinum Problem 1. Greedy Pie Eaters