비즈마켓
면접 대비시간 제한2초메모리 제한1024 MB
각 고객사에 아이템을 최대 하나씩 배정해 (A_i - B_j) 값의 합이 최대가 되도록 구합니다.
문제

비즈마켓은 기업을 주 고객으로 하는 온라인 종합상사입니다. 복지몰 사업, 기업 판촉 및 사은품 사업, 산업재 유통 사업을 운영합니다. 비즈마켓은 이 주력 분야 외에도 브랜드 사업, 렌탈 사업, 에너지 사업을 진행합니다. 비즈마켓의 기조는 "고객 기업 운영의 효율화에 기여하며, 그 구성원의 복지 만세를 추구한다"입니다. 신욱이는 비즈마켓으로부터 렌탈 사업을 효율적으로 운영하도록 도와 달라는 의뢰를 받았습니다.
비즈마켓에는 개의 물품이 있고, 물품 렌탈을 원하는 고객 기업이 개 있습니다. 각 물품은 만족도 를 가지고 있으며, 각 고객 기업은 의 비용을 지불하고 렌탈하려고 합니다. 각 고객 기업은 물품을 하나만 렌탈할 수 있고, 각 물품도 한 고객 기업에만 렌탈해 줄 수 있습니다.
만족도 인 물품을 비용 를 지불하려는 고객 기업에 렌탈해 주면 만큼의 고객 만족도를 얻습니다. 모든 고객 기업은 적어도 지불한 비용만큼의 만족도를 얻기를 원하므로, 고객 만족도가 보다 작아지면 거래를 진행하지 않습니다. 거래를 진행하지 않으면 고객 만족도도 얻을 수 없습니다.
신욱이가 해야 할 일은 각 고객 기업에 렌탈해 줄 물품을 정해 고객 만족도의 합을 최대로 만드는 것입니다. 하지만 신욱이는 과제가 너무 많아 이 일을 여러분에게 넘기고 떠났습니다. 신욱이를 대신해 고객 만족도 합의 최댓값을 구하세요.
입력
첫 번째 줄에 물품의 수 과 고객 기업의 수 이 공백으로 구분되어 주어집니다.
두 번째 줄에 각 물품의 만족도 이 공백으로 구분되어 주어집니다.
세 번째 줄에 고객 기업이 지불하려는 비용 이 공백으로 구분되어 주어집니다.
출력
첫 번째 줄에 각 고객 기업에 렌탈해 줄 물품을 골라 얻을 수 있는 고객 만족도 합의 최댓값을 출력합니다.
힌트
답이 int 범위를 넘을 수 있으니 64비트 정수 자료형(C/C++: long long, Java: long)을 사용해야 합니다.