package GreedyAlgo;

import java.util.Arrays;
import java.util.Collections;

public class ChocolaProblem {
    public static void main(String[] args) {
        int n =4 ,m=6;
        Integer costVer [] = {2,1,3,1,4};
        Integer costHor [] ={4,1,2};

        Arrays.sort(costHor, Collections.reverseOrder());
        Arrays.sort(costVer,Collections.reverseOrder());

        int h =0,v=0;
        int hp=1,vp=1;
        int finalcost=0;
        while(h < costHor.length && v < costVer.length){
            if(costVer[v] >= costHor[h] ){
                finalcost+=costVer[v]*hp;
                vp++;
                v++;
            }else{
                finalcost+=costHor[h]*vp;
                hp++;
                h++;
            }
        }
        while(h<costHor.length){
            finalcost+=costHor[h]*vp;
            h++;
            hp++;
        }
        while(v<costVer.length){
            finalcost+=costVer[v]*hp;
            v++;
            vp++;
        }
        System.out.println(finalcost);
    }
}