이벤트

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