My Solution
\n/**\n * Time Complexity: O(n * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `items`\n */\nclass Solution {\n public:\n  long l
```\n/**\n * Time Complexity: O(n * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `items`\n */\nclass Solution {\n public:\n  long long findMaximumElegance(vector<vector<int>> &items, const int k) {\n    const int n = static_cast<int>(items.size());\n    sort(items.begin(), items.end(), [](const vector<int> &lhs, const vector<int> &rhs) -> bool {\n      return lhs.front() > rhs.front();\n    });\n    \n    bool occupied_categories[n];\n    memset(occupied_categories, 0, sizeof(occupied_categories));\n    int categories = 0;\n    long long total = 0LL;\n    stack<int> removables;\n    for (int i = 0; i < k; ++i) {\n      const int profit = items[i].front();\n      const int category = items[i].back() - 1;\n      total += profit;\n      if (occupied_categories[category]) {\n        // removing the item `items[i]` will not cause the number of the categories to decrease\n        removables.emplace(profit);\n      } else {\n        occupied_categories[category] = true;\n        ++categories;\n      }\n    }\n    \n    long long ret = total + static_cast<long long>(categories) * categories;\n    for (int i = k; i < n && !removables.empty(); ++i) {\n      /**\n       * some explanations on the condition `!removables.empty()`\n       * assume that `removables` is empty,\n       * when a new item `items[i]` comes,\n       * no matter whether item `items[i]` has a different category\n       * among all categories of the owned items, excluding the item `items[i]`,\n       * or not, it\'s necessary to remove an existing item to\n       * keep the number of owned items `k`,\n       * which will cause the number of categories\n       * of the owned items, including the item `items[i]`,\n       * to unchange or decrease, which can not cause the elegance of the owned\n       * items to increase, so when `removables` is empty,\n       * it\'s unnecessary to continue\n       */\n      const int profit = items[i].front();\n      const int category = items[i].back() - 1;\n      if (occupied_categories[category]) {\n        /**\n         * 1. adding the item `items[i]` will not cause the number of the categories to increase\n         * 2. in order to keep the number of the owned items being `k`,\n         *    one owned item should be removed, the profit of any owned item is greater than or equal\n         *    to the profit of the item `items[i]`\n         * so adding the item `items[i]` will not increase the elegance of the owned items\n         */\n        continue;\n      }\n      \n      /**\n       * add the item `items[i]`, at the same time one owned item should be removed\n       */\n      total += profit;\n      total -= removables.top();\n      removables.pop();\n      occupied_categories[category] = true;\n      ++categories;\n      ret = max(ret, total + static_cast<long long>(categories) * categories);\n    }\n    return ret;\n  }\n};\n```
[]