Weighted LRU Cache: Capacity Counted by Item Quantity

Design a variant of the classic least-recently-used (LRU) cache. In the classic version, the capacity limits the number of items stored. In this variant, every item carries a positive integer quantity, and the capacity limits the total quantity across all stored items — an item with quantity 3 consumes 3 units of capacity, not 1. All other behavior (recency tracking, eviction order) is identical to a standard LRU cache.

Implement the class WeightedLRUCache:

• WeightedLRUCache(int capacity) — initializes the cache with a positive integer capacity, the maximum total quantity the cache may hold at any time.
• int get(int key) — if key exists in the cache, returns its value and marks the key as the most recently used; otherwise returns -1.
• void put(int key, int value, int quantity) — inserts or updates an entry:

1. If key already exists, overwrite its value and quantity, and mark it as the most recently used.
2. Otherwise, insert key as the most recently used entry.
3. Afterwards, while the sum of quantities of all stored items exceeds capacity, evict the least recently used item.

An evicted key is removed entirely; a later get on it returns -1 (and a later put re-inserts it as a fresh entry).

Example

Input:
["WeightedLRUCache", "put", "put", "get", "put", "get", "get"]
[[5], [1, 10, 2], [2, 20, 2], [1], [3, 30, 3], [2], [1]]

Output:
[null, null, null, 10, null, -1, 10]

Explanation (capacity = 5):

1. put(1, 10, 2) — cache holds {1}, total quantity 2.
2. put(2, 20, 2) — cache holds {1, 2}, total quantity 4.
3. get(1) returns 10 and makes key 1 the most recently used; key 2 is now the least recently used.
4. put(3, 30, 3) — total quantity would become 7 > 5, so the least recently used key 2 is evicted; cache holds {1, 3}, total quantity 5.
5. get(2) returns -1 (evicted).
6. get(1) returns 10.

Constraints

• 1 <= capacity <= 10^9
• 1 <= quantity <= capacity for every put call
• 0 <= key, value <= 10^9
• At most 2 * 10^5 calls will be made to get and put combined.

Performance requirement

Both get and put must run in average O(1) time. The eviction loop inside put is amortized O(1): every stored item is evicted at most once, so total eviction work is bounded by the total number of insertions.