이벤트

게임에서 특별 이벤트가 진행된다. 이벤트 기간 동안 총 $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$을 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 \le K \le N \le 200\,000$
• $1 \le S_i < E_i \le 10^9; 0 < P_i \le 10^9 ; 0 \le D_i \le 40\,000$ ($1 \le i \le N$)
• 아이템을 얻기 위해 필요한 행동력은 $0$ 이하로 떨어지지 않는다. 즉, $P_i > D_i \times (E_i - S_i)$이다.