class Solution {
  public long pickGifts(int[] gifts, int k) {
    var q = new PriorityQueue<Integer>(Comparator.reverseOrder());
    for (var gift : gifts) {
      q.offer(gift);
    }

    for (int i = 0; i < k; ++i) {
      int richest = q.poll();
      q.offer((int) Math.sqrt(richest));
    }

    long remaining = 0;
    while (!q.isEmpty()) {
      remaining += q.poll();
    }
    return remaining;
  }
}