비즈마켓

아직 제출이 없습니다시간 제한2초메모리 제한1024 MB

문제

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

비즈마켓에는 NN개의 물품이 있고, 물품을 렌탈하기를 원하는 MM개의 고객 기업이 있습니다. 각 물품은 A_iA\_i 의 만족도를 가지고 있으며, 각 고객 기업은 B_jB\_j 의 비용을 지불하여 렌탈을 진행하고자 합니다. 각 고객 기업은 하나의 물품만 렌탈할 수 있으며, 각 물품 또한 하나의 고객 기업에만 렌탈해줄 수 있습니다.

A_iA\_i 의 만족도를 가지는 물품을 B_jB\_j 의 비용을 지불하고자 하는 고객 기업에 렌탈해주게 되면 A_iB_jA\_i - B\_j 만큼의 고객 만족도를 얻을 수 있습니다. 모든 고객 기업들은 적어도 자신이 지불한 비용만큼의 만족도를 얻기를 원하기 때문에, 고객 만족도가 00보다 작아진다면 거래를 진행하지 않을 것입니다. 거래를 진행하지 않으면 당연히 고객 만족도도 얻을 수 없습니다.

신욱이가 구체적으로 해야 하는 일은 각 고객 기업에 렌탈해 줄 물품을 잘 정해서 고객 만족도의 합을 최대로 만드는 것입니다. 하지만 신욱이는 해야 할 과제가 너무 많았던 나머지, 이 일을 여러분들한테 넘기고 과제를 하러 떠나버렸습니다. 신욱이를 대신해 고객 만족도의 합의 최댓값을 구해줍시다.

입력

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

두 번째 줄에는 각 상품의 만족도 A_1,A_2,A_3,,A_NA\_1, A\_2, A\_3, \dots, A\_N 을 의미하는 정수 NN개가 공백으로 구분되어 주어집니다. (0A_i109)(0 \le A\_i \le 10^9)

세 번째 줄에는 고객 기업이 지불하고자 하는 비용 B_1,B_2,B_3,,B_MB\_1, B\_2, B\_3, \dots, B\_M 을 의미하는 정수 MM개가 공백으로 구분되어 주어집니다. (0B_j109)(0 \le B\_j \le 10^9)

출력

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

힌트

예제와 같이 답이 int 범위를 초과할 수 있으니, 64bit 정수 자료형 (C/C++: long long, Java: long)을 이용해야 합니다.