#include <bits/stdc++.h>

using namespace std;

struct KienHang {
	float m; //Khoi luong
	float k; //Kich thuoc
};

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

void Quick_Sort(KienHang 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 Truck(int k, KienHang *kh, int n, int *s, int count) {
	Quick_Sort(kh, 0, 4, false);
	int i = 0;
	while (k > 0 && i < n) {
		if (k >= kh[i].m) {
			s[i]++;
			k -= kh[i].m;
			count++;
		}
		i++;
	}
	return count;
}

int main() {
	int n = 5; //So luong kien hang
	int k = 20; //Kich thuoc thung xe
	int count = 0;
	KienHang kh[] = {
		{8, 3},
		{5, 4},
		{4, 5},
		{3, 6},
		{2, 2}
	};
	cout << "So luong kien hang: " << n << endl;
	cout << "Kich thuoc thung xe: " << k << endl;
	int *s = (int*)calloc(n, sizeof(int));
	count = Truck(k, kh, n, s, count);
	cout << "Ket qua: " << count << endl;
	if (count > 0) {
		for (int i = 0; i < n; i++) {
			if (s[i] == 1) cout << "Khoi luong: " << kh[i].m << " - Kich thuoc: " << kh[i].k << endl;
		}
	}
	return 0;
}