class Solution {

    class Node {
        double w_per_q;
        Double quality;

        public Node(double w_per_q, Double quality) {
            this.w_per_q = w_per_q;
            this.quality = quality;
        }

    }

    class MyCompByWageUnit implements Comparator<Node> {
        public int compare(Node n1, Node n2) {
            if (n1.w_per_q > n2.w_per_q) return 1;
            else if (n1.w_per_q < n2.w_per_q) return -1;
            else return 0;

        }
    }

    class MyCompReverse implements Comparator<Double> {
        public int compare(Double n1, Double n2) {
            if (n1 > n2) return -1;
            else if (n1 < n2) return +1;
            else return 0;
        }
    }

    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        // n 數量級
        // val 數字值大小

        // the basic unit pay will be decided by: max w/q
        // result: min( (max w/q) * total_combined_q )

        // sort w/q - we intend to go from smallest w/q first to the largest
        Node[] wage_units = new Node[wage.length];
        for (int i = 0; i < quality.length ;i++) {
            double q = quality[i];
            double w = wage[i];
            wage_units[i] = new Node(w/q, q);
        }

        Arrays.sort(wage_units, new MyCompByWageUnit());

        // int count = 0;
        Double result_min = Double.MAX_VALUE;
        Double q_sum = 0d;
        TreeSet<Double> set_quality_max = new TreeSet<>();
        // PriorityQueue<Double> pq_quality_max = new PriorityQueue<>(100, new MyCompReverse());
        for (int i = 0; i < wage_units.length ;i++) {

            if (i >= k) {
                // Double q_to_removed = pq_quality_max.poll();
                Double q_to_removed = set_quality_max.pollLast();
                q_sum -= q_to_removed; // attention: you need to maintian the top K elements
            }

            Node node_now = wage_units[i];
            Double wage_unit = node_now.w_per_q;
            double quality_now = node_now.quality;
            // pq_quality_max.offer(quality_now);
            if (set_quality_max.contains(quality_now)) {
                System.out.println("you cannot use TreeSet cuz there is DUPLICATE!");
            }
            set_quality_max.add(quality_now);
            q_sum += quality_now; // attention: you need to maintian the top K elements
                                  // attention: and the reason you don't have to pop K elements every time, is cuz you MUST add the i number since it has the max_wageUnit here in the leetcode question

            if (i >= k - 1) {
                // record result now
                result_min = Math.min(result_min, wage_unit * q_sum);
            }

        } // end of if

        return result_min;
    }

}