# Chọn món ăn

Bài toán này ta sẽ sử dụng thuật toán tham lam với tư tưởng như sau:
- Nếu chưa chọn đủ $k$ món khác nhau thì sẽ duyệt từng người có món ăn trùng với người khác và thay đổi bằng món mới có giá trị nhỏ nhất mà lớn hơn giá trị của người đó, đồng thời chưa có ai chọn.
- Người được chọn sẽ là người có chi phí cần sử dụng nhỏ nhất.

### Subtask 1

Vì tất cả $a_i$ đều bằng nhau nên ta sẽ chọn $k-1$ món ăn có giá trị nhỏ nhất mà lớn hơn giá trị $a_i$ để gán cho $k-1$ người là ta sẽ có đủ $k$ món khác nhau. Do đó ta chỉ cần sort sau đó lấy $k-1$ món ăn có giá trị lớn hơn giá trị của món ăn $a_i$.

### Subtask 2

Ta sort các món ăn theo giá trị rồi sử dụng hai con trỏ để chọn ra món cần đổi cho mỗi người có món ăn trùng với người khác.

### Subtask 3

Ta sử dụng quy hoạch động $bitmask$ mà không cần tham lam.

### Subtask 4

Ta sẽ duyệt từng món ăn có giá trị lớn nhất đến các món có giá trị nhỏ nhất, với mỗi món ăn có nhiều người cùng lựa chọn, ta sẽ tìm món ăn chưa có ai chọn gần nhất để đổi.

Việc tìm kiếm này có thể dùng $stack$ hoặc $DSU$ để tìm kiếm.

### Subtask 5

Sau khi sắp xếp, những món ăn có giá trị gần nhau sẽ nằm gần nhau, vậy nên cần dùng thêm multiset để tìm kiếm tối ưu nhất.

### Code

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second

int n, m, k;
const int Sz = 2e5 + 2;
int a[Sz + 1];
pair <pair <int, int>, int> ppp[Sz + 1];
int c[Sz + 1];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#define task "CMA"
	if(fopen(task".inp", "r")){
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= m; i++){
		cin >> ppp[i].fi.fi;
		ppp[i].fi.se = i;
	}
	sort(ppp + 1, ppp + m + 1);
	for(int i = 1; i <= m; i++) c[i] = ppp[i].fi.fi;
	for(int i = 1; i <= m; i++) ppp[i].se = i;
	sort(ppp + 1, ppp + m + 1, [&](const pair <pair <int, int>, int> &A, const pair <pair <int, int>, int> &B){
		return A.fi.se < B.fi.se;
	});
	for(int i = 1; i <= n; i++) a[i] = ppp[a[i]].se;
	
	sort(a + 1, a + n + 1);
	vector <pair <int, int> > v;
	int last = a[1]; int cnt = 1;

	for(int i = 2; i <= n; i++){
		if(a[i] == last) cnt++;
		else{
			v.push_back(make_pair(last, cnt));
			last = a[i]; cnt = 1;
		}
	}
	v.push_back(make_pair(last, cnt));
	multiset <int> notchosen;
	for(int i = 1; i <= m; i++) notchosen.insert(c[i]);
	for(auto i : v) notchosen.erase(notchosen.find(c[i.fi]));
	vector <int> ress;
	pair <int, int> p;
	multiset <int>::iterator it;
	for(int t = (int)v.size() - 1; t >= 0; t--){
		p = v[t];
		for(int i = 1; i < p.se; i++){
			it = notchosen.upper_bound(c[p.fi]);
			if(it != notchosen.end()){
				ress.push_back((*it) - c[p.fi]);
				notchosen.erase(notchosen.find(*it));
			}
		}
	}
	int alrhas = (int)v.size();
	if(k <= alrhas){
		cout << 0; return 0;
	}
	//cout << "con\n";
	//k > alrhas
	k -= alrhas;
	int res = 0;
	sort(ress.begin(), ress.end());
	if((int)ress.size() < k){
		cout << -1;
		return 0;
	}
	for(int i = 0; i < k; i++) res += ress[i];
	cout << res;
}