만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

비즈마켓

면접 대비

시간 제한2초메모리 제한1024 MB

요약
각 고객사에 아이템을 최대 하나씩 배정해 (A_i - B_j) 값의 합이 최대가 되도록 구합니다.
난이도

보통10점 중 4점

유형
그리디, 정렬
정답자
아직 제출이 없습니다

문제

비즈마켓은 기업을 주 고객으로 하는 온라인 종합상사입니다. 복지몰 사업, 기업 판촉 및 사은품 사업, 산업재 유통 사업을 운영합니다. 비즈마켓은 이 주력 분야 외에도 브랜드 사업, 렌탈 사업, 에너지 사업을 진행합니다. 비즈마켓의 기조는 "고객 기업 운영의 효율화에 기여하며, 그 구성원의 복지 만세를 추구한다"입니다. 신욱이는 비즈마켓으로부터 렌탈 사업을 효율적으로 운영하도록 도와 달라는 의뢰를 받았습니다.

비즈마켓에는 NN개의 물품이 있고, 물품 렌탈을 원하는 고객 기업이 MM개 있습니다. 각 물품은 만족도 AiA_i를 가지고 있으며, 각 고객 기업은 BjB_j의 비용을 지불하고 렌탈하려고 합니다. 각 고객 기업은 물품을 하나만 렌탈할 수 있고, 각 물품도 한 고객 기업에만 렌탈해 줄 수 있습니다.

만족도 AiA_i인 물품을 비용 BjB_j를 지불하려는 고객 기업에 렌탈해 주면 Ai−BjA_i - B_j만큼의 고객 만족도를 얻습니다. 모든 고객 기업은 적어도 지불한 비용만큼의 만족도를 얻기를 원하므로, 고객 만족도가 00보다 작아지면 거래를 진행하지 않습니다. 거래를 진행하지 않으면 고객 만족도도 얻을 수 없습니다.

신욱이가 해야 할 일은 각 고객 기업에 렌탈해 줄 물품을 정해 고객 만족도의 합을 최대로 만드는 것입니다. 하지만 신욱이는 과제가 너무 많아 이 일을 여러분에게 넘기고 떠났습니다. 신욱이를 대신해 고객 만족도 합의 최댓값을 구하세요.

입력

첫 번째 줄에 물품의 수 NN과 고객 기업의 수 MM이 공백으로 구분되어 주어집니다. (1≤N,M≤2×105)(1 \le N, M \le 2 \times 10^5)

두 번째 줄에 각 물품의 만족도 A1,A2,…,ANA_1, A_2, \dots, A_N이 공백으로 구분되어 주어집니다. (0≤Ai≤109)(0 \le A_i \le 10^9)

세 번째 줄에 고객 기업이 지불하려는 비용 B1,B2,…,BMB_1, B_2, \dots, B_M이 공백으로 구분되어 주어집니다. (0≤Bj≤109)(0 \le B_j \le 10^9)

출력

첫 번째 줄에 각 고객 기업에 렌탈해 줄 물품을 골라 얻을 수 있는 고객 만족도 합의 최댓값을 출력합니다.

힌트

답이 int 범위를 넘을 수 있으니 64비트 정수 자료형(C/C++: long long, Java: long)을 사용해야 합니다.

예제2

  1. 예제 1

    입력
    5 5
    6 7 8 9 10
    2 3 4 5 6
    
    예상 출력
    20
    
  2. 예제 2

    입력
    5 3
    927291536 144432154 222251432 846751354 648975123
    105423157 28465 1354216
    
    예상 출력
    2316212175