Implement a cache with following property:

1. Cache will have a max capacity.
2. Cache will store an item with a key, value, priority and the expires at time.
3. While inserting any item, if the cache is not full item will get inserted in cache. Also if the item with same key is already there, it will get replaced with updated value, priority and expiry.
4. On getting an item it will become most recently used item.
5. If cache is full while inserting, the following eviction policy will apply.
   a. Get the expiration time threshold by calling api GetExpiryThreshold(), the item with lower expiry time than threshold will get removed.
   b. if there are more than one item, then the oldest expiry item gets removed.
   c. if there are multiple items with oldest expiry, then the least priority item gets removed
   d. otherwise if there are multiple items with same priority, remove item which was least recently used.

Ex-
GetExpiryThreshold() => returns a random value in range [0, 100000]

cache = new Cache(5)
cache.Set(key:"A", value:5, priority:1, expiry: 1000)
// [A]
cache.Set(key:"B", value:15, priority:5, expiry: 500)
// [B, A]
cache.Set(key:"C", value:0, priority:5, expiry: 2000)
// [C, B, A]
cache.Set(key:"D", value:1, priority:5, expiry: 2000)
// [D, C, B, A]
cache.Set(key:"E", value:10, priority:5, expiry: 3000)
// [E, D, C, B, A]
cache.Get("C") // returns 0
// [C, E, D, B, A]
cache.Set(key:"F", value:15, priority:5, expiry: 1000) // since cache is full here expiry threshold applies, ex- if it returned 600, then B gets evicted and F gets inserted
// [F, C, E, D, A]
cache.Set(key:"G", value:0, priority:5, expiry: 2000) // again assume threshold returned 600 then none of the items expired, so the least priority item i.e. A gets evicted and G inserted
// [G, F, C, E, D]
cache.Set(key:"H", value:1, priority:1, expiry: 2000) // assuming threshold as 600, here none expired and all items have same priority, so least recently item D gets evicted
// [H, G, F, C, E]
cache.Get("D") // throw exception as D is not present in cache
cache.Set(key:"I", value:10, priority:2, expiry: 2000) // assuming threshold is 2000, the oldest expired item is F:1000, it gets evicted and I inserted
// [I, H, G, C, E]
cache.Set(key:"E", value:10, priority:2, expiry: 2000) // since E is already there no eviction
// [E, I, H, G, C]
cache.Set(key:"M", value:10, priority:1, expiry: 3000) // asuming threshold as 2000, all the items have same expiry so least priority H will get evicted
// [M, E, I, G, C]

Implement this data structure with optimal Set and Get Operations. Assume that external api has constant time complexity.