#P4360. achievement

    ID: 3240 传统题 1000ms 512MiB 尝试: 40 已通过: 12 难度: 9 上传者: 标签>CF2800省选/NOI-排序贪心交换论证交替路根号分块整块懒标记直线上包络单调栈前后缀最值Lydsy3953

achievement

题目描述

有 nn 个成就,对于第 ii 个成就,它的初始难度为 aia_i,之后每秒难度会增加 bib_i。

你每秒钟都可以完成任意一个还未完成的成就,求完成 kk 个成就的总难度最小是多少。

另外,本题还有一个参数 modemode。如果 modemode 为 true\texttt{true},则你可以在一开始将某个成就的难度降为 00。

输入格式

第一行三个整数 n,k,moden,k,mode,分别表示成就数量,完成成就数量,和参数。

接下来 nn 行,每行两个整数 ai,bia_i,b_i,分别表示一个成就的初始难度,和每秒增加的难度。

输出格式

一行一个整数,描述答案。

3 3 0
0 1
1 2
2 3
7

提示

对于 100%100\% 的数据,1≤n≤1051\le n\le 10^5,0≤ai,bi≤1060\le a_i,b_i\le 10^6。

题目来源

Lydsy3953 Control\texttt{Lydsy3953 Control}