305649: CF1070C. Cloud Computing
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Cloud Computing
题意翻译
## 题目描述 $\text{Buber}$ 是一家致力于浪费投资者的钱的 $\text{Berland}$ 技术公司。最近，$\text{Buber}$ 决定将他的设施转移到云端。公司决定连续$\ n\ $天云端租用$\text{CPU}$。$\text{Buber}$每天都要租用$\ k\ $个$\text{CPU}$。 云端供应商提供$\ m\ $个租用计划，第$i$个计划有如下的特征： - $l_i,r_i$ 表示第$\ i\ $个计划从第$\ l_i\ $天开始，第$\ r_i\ $天结束。 - $c_i$ 表示第$\ i\ $个计划中，每天最多租用$\text{CPU}$个数。 - $p_i$ 表示第$\ i\ $个计划中，租用一个$\text{CPU}$一天的花费。 $\text{Buber}$ 可以同时使用多个计划，即他可以在第$\ x\ $天在每个进行中的计划（即$l_i≤x≤r_i$）中租用 $[0,c_i]$个$\text{CPU}$. 现在$\text{Buber}$告诉你正整数$\ k\ $，表示每天所需的$\text{CPU}$个数（如果某一天无论怎么租用都不能租到$\ k\ $个，他也希望租尽量多的$\text{CPU}$）。请你告诉他，他在这$\ n\ $天中最少需要花费多少钱来租用$\text{CPU}$？ ## 输出输入格式 ### 输入格式 第一行，三个正整数 $n,k,m\ $ ($1≤n,k≤10^6,1≤m≤2$ ⋅ $10^5$)，意义如上； 下面 $m$ 行，每行四个正整数表示$\ l_i,r_i,c_i,p_i$($1≤l_i≤r_i≤n,1≤c_i≤p_i≤10^6$)即第$\ i\ $个计划的特征。 ### 输出格式 仅一个正整数表示$\text{Buber}$最少可以花费的钱。题目描述
Buber is a Berland technology company that specializes in waste of investor's money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for $ n $ consecutive days, which are numbered from $ 1 $ to $ n $ . Buber requires $ k $ CPU cores each day. The cloud provider offers $ m $ tariff plans, the $ i $ -th tariff plan is characterized by the following parameters: - $ l_i $ and $ r_i $ — the $ i $ -th tariff plan is available only on days from $ l_i $ to $ r_i $ , inclusive, - $ c_i $ — the number of cores per day available for rent on the $ i $ -th tariff plan, - $ p_i $ — the price of renting one core per day on the $ i $ -th tariff plan. Buber can arbitrarily share its computing core needs between the tariff plans. Every day Buber can rent an arbitrary number of cores (from 0 to $ c_i $ ) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day. Find the minimum amount of money that Buber will pay for its work for $ n $ days from $ 1 $ to $ n $ . If on a day the total number of cores for all available tariff plans is strictly less than $ k $ , then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly $ k $ cores this day.输入输出格式
输入格式
The first line of the input contains three integers $ n $ , $ k $ and $ m $ ( $ 1 \le n,k \le 10^6, 1 \le m \le 2\cdot10^5 $ ) — the number of days to analyze, the desired daily number of cores, the number of tariff plans. The following $ m $ lines contain descriptions of tariff plans, one description per line. Each line contains four integers $ l_i $ , $ r_i $ , $ c_i $ , $ p_i $ ( $ 1 \le l_i \le r_i \le n $ , $ 1 \le c_i, p_i \le 10^6 $ ), where $ l_i $ and $ r_i $ are starting and finishing days of the $ i $ -th tariff plan, $ c_i $ — number of cores, $ p_i $ — price of a single core for daily rent on the $ i $ -th tariff plan.
输出格式
Print a single integer number — the minimal amount of money that Buber will pay.
输入输出样例
输入样例 #1
5 7 3
1 4 5 3
1 3 5 2
2 5 10 1
输出样例 #1
44
输入样例 #2
7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8
输出样例 #2
462
输入样例 #3
4 100 3
3 3 2 5
1 1 3 2
2 4 4 4
输出样例 #3
64