| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 32 | 12 | 11 | 45.833% |
게임에서 특별 이벤트가 진행된다. 이벤트 기간 동안 총 $N$개의 아이템이 등장하며, $i$번째 아이템은 $S_i$번째 날부터 $E_i$번째 날까지 획득할 수 있다. 이 아이템을 얻는 데 필요한 행동력은 첫날에는 $P_i$이고, 이후 하루가 지날 때마다 $D_i$만큼 감소한다. 따라서 $S_i \le t \le E_i$인 날 $t$에 필요한 행동력은 $P_i - D_i \times (t - S_i)$이며, 항상 $0$보다 크다.
참여자는 이벤트 기간 중에 단 하루만 참여할 수 있으며, 그 날 획득 가능한 아이템은 모두 동시에 얻어야 한다.
이벤트 보상을 받기 위해서는 최소 $K$개의 아이템을 확보해야 한다. 당신은 이벤트 보상을 받기 위해 필요한 행동력의 총합이 최소가 되도록 참여 일자를 선택할 때, 필요한 행동력의 총합을 구하여라. 만약 어떤 날을 선택해도 $K$개 이상의 아이템을 얻을 수 없다면, $-1$을 출력한다.
첫 번째 줄에 두 정수 $N$, $K$가 공백으로 구분되어 주어진다.
다음 $N$개의 줄에 $i$번째 아이템의 정보를 나타내는 네 정수 $S_i$, $E_i$, $P_i$, $D_i$가 공백으로 구분되어 주어진다.
$K$개 이상의 아이템을 얻기 위해 필요한 행동력의 총합을 출력한다. $K$개 이상의 아이템을 얻는 것이 불가능하면 $-1$을 출력한다.
3 2 1 4 10 3 2 3 5 1 2 5 10 2
7
2번째 날에 참여하면 모든 아이템을 얻어야 하고, 필요한 행동력은 $7+5+10=22$이다.
4번째 날에 참여하면 1, 3번 아이템을 얻고, 필요한 행동력은 $1+6=7$로 최소이다.
2 2 1 2 5 1 3 4 9 5
-1