#include <bits/stdc++.h>

using namespace std;

struct GoiHang {
	float m; //Khoi luong
	float s; //Kich thuoc
};

void Swap(GoiHang &a, GoiHang &b) {
	GoiHang tmp = a;
	a = b;
	b = tmp;
}

void Quick_Sort(GoiHang a[], int left, int right, bool asc = true) {
	float pivot = a[(left + right) / 2].m;
	int i = left;
	int j = right;
	while (i < j) {
		while (a[i].m < pivot == asc) {
			i++;
		}
		while (a[j].m > pivot == asc) {
			j--;
		}
		if (i <= j) {
			Swap(a[i], a[j]);
			i++;
			j--;
		}
	}
	if (i < right) {
		Quick_Sort(a, i, right, asc);
	}
	if (left < j) {
		Quick_Sort(a, left, j, asc);
	}
}

int Balo(int k, GoiHang *gh, int n, int *s, int sum) {
	Quick_Sort(gh, 0, 4, true);
	int i = 0;
	while (k > 0 && i < n) {
		if (k >= gh[i].s) {
			s[i]++;
			k -= gh[i].s;
			sum += gh[i].s;
		}
		i++;
	}
	return sum;
}

int main() {
	int n = 5; //So luong goi hang
	int k = 20; //Kich thuoc balo
	int sum = 0;
	GoiHang gh[] = {
		{8, 3},
		{5, 4},
		{4, 5},
		{3, 8},
		{2, 2}
	};
	cout << "So luong goi hang: " << n << endl;
	cout << "Kich thuoc balo: " << k << endl;
	int *s = (int*)calloc(n, sizeof(int));
	sum = Balo(k, gh, n, s, sum);
	cout << "Ket qua: " << sum << endl;
	if (sum > 0) {
		for (int i = 0; i < n; i++) {
			if (s[i] == 1) cout << "Khoi luong: " << gh[i].m << " - Kich thuoc: " << gh[i].s << endl;
		}
	}
	return 0;
}