#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

// Khai báo cấu trúc dữ liệu cho chiếc Quạt
struct Quat {
    string tenHang;
    string mauSac;
    long giaBan;
};

// Hàm so sánh để sắp xếp quạt theo giá tăng dần
bool soSanhGia(Quat a, Quat b) {
    return a.giaBan < b.giaBan;
}

int main() {
    // 1. Khởi tạo dữ liệu
    long p; // Số tiền đang có
    int n;  // Số lượng quạt trong danh sách
    
    cout << "Nhap so tien p ban co (0 < p < 1200000): ";
    cin >> p;
    cout << "Nhap so luong quat n (5 < n < 12): ";
    cin >> n;

    vector<Quat> danhSachQuat(n);

    // Nhập dữ liệu mẫu hoặc nhập từ bàn phím
    // Ở đây mình ví dụ nhập mẫu để bạn dễ chạy thử ngay
    danhSachQuat = {
        {"Panasonic", "Trang", 450000},
        {"Senko", "Xanh", 250000},
        {"Asia", "Xam", 300000},
        {"Mitsubishi", "Den", 800000},
        {"Toshiba", "Trang", 600000},
        {"Lifan", "Do", 200000}
    };
    
    // Nếu n khác số lượng mẫu trên, bạn có thể nhập thêm bằng vòng lặp:
    // for(int i=0; i<n; i++) { ... cin >> ... }

    // 2. Thực hiện chiến lược Tham lam
    // Sắp xếp quạt theo giá từ thấp đến cao
    sort(danhSachQuat.begin(), danhSachQuat.end(), soSanhGia);

    vector<Quat> ketQuaMua;
    long soTienGoc = p;
    int tongSoQuat = 0;

    for (int i = 0; i < n; i++) {
        if (p >= danhSachQuat[i].giaBan) {
            p -= danhSachQuat[i].giaBan; // Trừ tiền
            ketQuaMua.push_back(danhSachQuat[i]); // Thêm vào giỏ hàng
            tongSoQuat++;
        }
    }

    // 3. Hiển thị kết quả
    cout << "\n===========================================" << endl;
    cout << "Voi so tien " << soTienGoc << " VND, ban co the mua toi da " << tongSoQuat << " chiec quat." << endl;
    cout << "Danh sach quat da mua:" << endl;
    cout << left << setw(20) << "Ten Hang" << setw(15) << "Gia Ban" << endl;
    cout << "-------------------------------------------" << endl;
    
    for (const auto& q : ketQuaMua) {
        cout << left << setw(20) << q.tenHang << setw(15) << q.giaBan << " VND" << endl;
    }
    cout << "-------------------------------------------" << endl;
    cout << "So tien con du: " << p << " VND" << endl;
    cout << "===========================================" << endl;

    return 0;
}