시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB32121145.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$을 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $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)$이다.

예제 입력 1

3 2
1 4 10 3
2 3 5 1
2 5 10 2

예제 출력 1

7

2번째 날에 참여하면 모든 아이템을 얻어야 하고, 필요한 행동력은 $7+5+10=22$이다.

4번째 날에 참여하면 1, 3번 아이템을 얻고, 필요한 행동력은 $1+6=7$로 최소이다.

예제 입력 2

2 2
1 2 5 1
3 4 9 5

예제 출력 2

-1
W3sicHJvYmxlbV9pZCI6IjM0MzE1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc0XHViY2E0XHVkMmI4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVkMmI5XHViY2M0IFx1Yzc3NFx1YmNhNFx1ZDJiOFx1YWMwMCBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YmNhNFx1ZDJiOCBcdWFlMzBcdWFjMDQgXHViM2Q5XHVjNTQ4IFx1Y2QxZCAkTiRcdWFjMWNcdWM3NTggXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YmE3MCwgJGkkXHViYzg4XHVjOWY4IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0MCAkU19pJFx1MjAwYlx1YmM4OFx1YzlmOCBcdWIwYTBcdWJkODBcdWQxMzAgJEVfaSRcdTIwMGJcdWJjODhcdWM5ZjggXHViMGEwXHVhZTRjXHVjOWMwIFx1ZDY4ZFx1YjRkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YzViYlx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDU4OVx1YjNkOVx1YjgyNVx1Yzc0MCBcdWNjYWJcdWIwYTBcdWM1ZDBcdWIyOTQgJFBfaSRcdTIwMGJcdWM3NzRcdWFjZTAsIFx1Yzc3NFx1ZDZjNCBcdWQ1NThcdWI4ZThcdWFjMDAgXHVjOWMwXHViMGEwIFx1YjU0Y1x1YjljOFx1YjJlNCAkRF9pJFx1MjAwYlx1YjljY1x1ZDA3YyBcdWFjMTBcdWMxOGNcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyAkU19pIFxcbGUgdCBcXGxlIEVfaSRcdWM3NzggXHViMGEwICR0JFx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNTg5XHViM2Q5XHViODI1XHVjNzQwICRQX2kgLSBEX2kgXFx0aW1lcyAodCAtIFNfaSkkXHVjNzc0XHViYTcwLCBcdWQ1NmRcdWMwYzEgJDAkXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzM4XHVjNWVjXHVjNzkwXHViMjk0IFx1Yzc3NFx1YmNhNFx1ZDJiOCBcdWFlMzBcdWFjMDQgXHVjOTExXHVjNWQwIFx1YjJlOCBcdWQ1NThcdWI4ZThcdWI5Y2MgXHVjYzM4XHVjNWVjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWRmOCBcdWIwYTAgXHVkNjhkXHViNGRkIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDAgXHViYWE4XHViNDUwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM1YmJcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWJjYTRcdWQyYjggXHViY2Y0XHVjMGMxXHVjNzQ0IFx1YmMxYlx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjZDVjXHVjMThjICRLJFx1YWMxY1x1Yzc1OCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVkNjU1XHViY2Y0XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1Yzc3NFx1YmNhNFx1ZDJiOCBcdWJjZjRcdWMwYzFcdWM3NDQgXHViYzFiXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNTg5XHViM2Q5XHViODI1XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1Y2MzOFx1YzVlYyBcdWM3N2NcdWM3OTBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTYwIFx1YjU0YywgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDU4OVx1YjNkOVx1YjgyNVx1Yzc1OCBcdWNkMWRcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLiBcdWI5Y2NcdWM1N2QgXHVjNWI0XHViNWE0IFx1YjBhMFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NzRcdWIzYzQgJEskXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQsICQtMSRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCAkTiQsICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgJGkkXHViYzg4XHVjOWY4IFx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggJFNfaSQsICRFX2kkLCAkUF9pJCwgJERfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JEskXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVjNWJiXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVkNTg5XHViM2Q5XHViODI1XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuICRLJFx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YzViYlx1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTU4XHViYTc0ICQtMSRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG48bGk+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48bGk+JDEgXFxsZSBLIFxcbGUgTiBcXGxlIDIwMFxcLDAwMCQ8XC9saT5cclxuPGxpPiQxIFxcbGUgU19pICZsdDsgRV9pIFxcbGUgMTBeOTsgMCAmbHQ7IFBfaSBcXGxlIDEwXjkgOyAwIFxcbGUgRF9pIFxcbGUgNDBcXCwwMDAkICgkMSBcXGxlIGkgXFxsZSBOJCk8XC9saT5cclxuPGxpPlx1YzU0NFx1Yzc3NFx1ZDE1Y1x1Yzc0NCBcdWM1YmJcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ1ODlcdWIzZDlcdWI4MjVcdWM3NDAgJDAkIFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWI1YThcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM5ODksICRQX2kgJmd0OyBEX2kgXFx0aW1lcyAoRV9pIC0gU19pKSRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+Mlx1YmM4OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTU4XHViYTc0IFx1YmFhOFx1YjRlMCBcdWM1NDRcdWM3NzRcdWQxNWNcdWM3NDQgXHVjNWJiXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDU4OVx1YjNkOVx1YjgyNVx1Yzc0MCAkNys1KzEwPTIyJFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+NFx1YmM4OFx1YzlmOCBcdWIwYTBcdWM1ZDAgXHVjYzM4XHVjNWVjXHVkNTU4XHViYTc0IDEsIDNcdWJjODggXHVjNTQ0XHVjNzc0XHVkMTVjXHVjNzQ0IFx1YzViYlx1YWNlMCwgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1ZDU4OVx1YjNkOVx1YjgyNVx1Yzc0MCAkMSs2PTckXHViODVjIFx1Y2Q1Y1x1YzE4Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzNDMxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV2ZW50cyBpbiBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5TcGVjaWFsIGV2ZW50cyB3aWxsIHRha2UgcGxhY2UgaW4gYSBnYW1lLiBUaGVyZSB3aWxsIGJlICROJCBldmVudCBpdGVtcywgYW5kIHRoZSAkaSQtdGggaXRlbSB3aWxsIGJlIGF2YWlsYWJsZSBmcm9tIGRheSAkU19pJCB0byBkYXkgJEVfaSQsIGluY2x1c2l2ZS4gVG8gb2J0YWluIHRoZSBpdGVtLCBhIHJlcXVpcmVkIGVuZXJneSBpcyAkUF9pJCBvbiB0aGUgZmlyc3QgZGF5LCBhbmQgaXQgZGVjcmVhc2VzIGJ5ICREX2kkIGVhY2ggZGF5LiBIZW5jZSwgb24gZGF5ICR0JCB3aXRoICRTX2kgXFxsZSB0IFxcbGUgRV9pJCwgdGhlIHJlcXVpcmVkIGVuZXJneSB3b3VsZCBiZSAkUF9pIC0gRF9pIFxcdGltZXMgKHQgLSBTX2kpJCB3aGljaCBpcyBhbHdheXMgZ3JlYXRlciB0aGFuICQwJC48XC9wPlxyXG5cclxuPHA+QSBwbGF5ZXIgY2FuIHBhcnRpY2lwYXRlIGluIHRoZSBldmVudCBvbmx5IG9uIG9uZSBkYXksIGFuZCB0aGUgcGxheWVyIG11c3Qgb2J0YWluIGFsbCBvZiB0aGUmbmJzcDtpdGVtcyB0aGF0IGFyZSBhdmFpbGFibGUgb24gdGhhdCBkYXkuPFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIHJlY2VpdmUgdGhlIGV2ZW50IHJld2FyZCwgYSBwbGF5ZXIgbXVzdCBvYnRhaW4gYXQgbGVhc3QgJEskIGl0ZW1zLiBZb3Ugd2FudCB0byBtaW5pbWl6ZSB0aGUgdG90YWwgcmVxdWlyZWQgZW5lcmd5IGluIG9yZGVyIHRvIG9idGFpbiB0aGUgZXZlbnQgcmV3YXJkIC0tIHRoaXMgaXMgd2hhdCB5b3UgbmVlZCB0byBjb21wdXRlLiBJZiB5b3UgY2Fubm90IG9idGFpbiAkSyQgb3IgbW9yZSBpdGVtcyByZWdhcmRsZXNzIG9mIHdoaWNoIGRheSB5b3UgcGFydGljaXBhdGUsIHRoZW4gb3V0cHV0ICQtMSQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gJE4kIGFuZCAkSyQsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICROJCBsaW5lcyB3aWxsIGNvbnRhaW4gZm91ciBpbnRlZ2VycyAkU19pJCwgJEVfaSQsICRQX2kkLCBhbmQgJERfaSQsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLCBkZXNjcmliaW5nIGl0ZW0gJGkkJiMzOTtzIHByb3BlcnRpZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtaW5pbXVtIGVuZXJneSBuZWVkZWQgdG8gb2J0YWluICRLJCBvciBtb3JlIGl0ZW1zLiBJZiBpdCYjMzk7cyBpbXBvc3NpYmxlLCBvdXRwdXQgJC0xJC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPkFsbCBudW1iZXJzIGluIHRoZSBpbnB1dCB3aWxsIGJlIGludGVnZXJzLjxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlIEsmbmJzcDtcXGxlIE4mbmJzcDtcXGxlIDIwMFxcLDAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZSBTX2kgJmx0OyBFX2kgXFxsZSAxMF45OyZuYnNwOzAgJmx0O1BfaSBcXGxlIDEwXjkmbmJzcDs7IDAgXFxsZSZuYnNwO0RfaSBcXGxlIDQwXFwsMDAwJCZuYnNwOygkMSBcXGxlIGkgXFxsZSBOJCk8XC9saT5cclxuXHQ8bGk+VGhlIHJlcXVpcmVkIGVuZXJneSBmb3IgYW55IGl0ZW0gb24gYW55IGRheSB3aWxsIG5ldmVyIGJlIGxlc3MgdGhhbiBvciBlcXVhbCB0byZuYnNwOyQwJC4gVGhhdCBpcywmbmJzcDskUF9pICZndDsgRF9pIFxcdGltZXMgKEVfaSAtIFNfaSkkIGZvciBhbGwgJGkkLjxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPk9uIERheSAyLCB0aGUgcGxheWVyIG11c3Qgb2J0YWluIGFsbCBpdGVtcywgYW5kIHRoZSByZXF1aXJlZCBlbmVyZ3kgd2lsbCBiZSAkNys1KzEwPTIyJC48XC9wPlxyXG5cclxuPHA+T24gRGF5IDQsIHRoZSBwbGF5ZXIgbXVzdCBvYnRhaW4gaXRlbSAxIGFuZCBpdGVtIDMsIGFuZCB0aGUgcmVxdWlyZWQgZW5lcmd5IHdpbGwgYmUgJDErNj03JCB3aGljaCBpcyBvcHRpbWFsLjxcL3A+XHJcbiJ9XQ==