TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4877
  • Problem
  • P4877灯泡
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,128m
    Description

    何老板装修新房子。
    房子有n个房间,何老板安排你在每个房间安装一盏灯。每间房间都需要不少于一定功率的灯泡才可以完全照亮。
    何老板事先已经买了n盏灯,你可以直接使用它们。你也可以去附近的商店换新灯泡,商店里所有正整数功率的灯泡都有售。但由于背包空间有限,你至多只能换k个灯泡。
    你需要找到一个合理的方案使得每个房间都被完全照亮,何老板想尽可能的省电。所以在每个房间都被完全照亮这个前提下使得n个灯泡的总功率尽可能小。

    Input Format

    第一行两个整数n,k(1<=k<=n<=500000)。
    第二行n个整数p[i]( \(1<=p[i]<=10^9\) ),表示现有的每个灯泡的功率。
    第三行n个整数w[i]( \(1<=w[i]<=10^9\) ),表示照亮每间房间所需要的最小功率。

    Output Format

    如果无法照亮每间房间,仅输出NIE。
    否则输出最小的总功率。

    Sample Input 1

    11 5
    1 2 7 8 10 11 16 18 20 21 22
    3 4 5 6 9 12 13 14 15 17 19

    Sample Output 1

    125

    Sample Input 2

    10 2
    6 4 3 7 3 6 1 3 5 7
    3 6 4 5 5 8 8 5 6 1

    Sample Output 2

    55

    Sample Input 3

    6 2
    12 1 7 5 2 10
    1 4 11 4 7 5

    Sample Output 3

    33

    Sample Input 4

    5 3
    1 2 3 4 5
    6 7 8 9 10

    Sample Output 4

    NIE

    Hint

    样例3解释:将2和10换成4和4。配对方案为1-1,4-4,4-4,5-5,7-7,11-12。


    Source  bzoj 3728 PA2014 Final Zarowki