public class TextileFactory {
    /*
     * Design an algorithm that determines the best return on the X*Y piece of
     * cloth.
     * 
     * X, Y represent the dimensions of the cloth. For the i-th dress, a[i]*b[i] is
     * the dimension of the cloth needed to make it, and p[i] is its selling price.
     * 
     * @returns The maximum sumed selling price of the dresses.
     */
    public static int clothCutting(int X, int Y, int[] a, int[] b, int[] p) {
        // TODO
        return -1;
    }

    public static void main(String[] args) {
        /*
         * Example 1
         */
        {
            int X = 5;
            int Y = 4;
            // Dress 1: 2x2 cloth needed, worth $100
            // Dress 2: 1x1 cloth needed, worth $1
            int[] a = { 2, 1 };
            int[] b = { 2, 1 };
            int[] p = { 100, 1 };
            // The optimal way is to make 4 of the first dress,
            // and use the rest of the cloth to make the second.
            System.out.println(clothCutting(X, Y, a, b, p));
        }

        /*
         * Example 2
         */
        {
            int X = 4;
            int Y = 4;
            // Dress 1: 4x4 cloth needed, worth $15
            // Dress 2: 3x3 cloth needed, worth $30
            // Dress 3: 1x4 cloth needed, worth $10
            int[] a = { 4, 3, 1 };
            int[] b = { 4, 3, 4 };
            int[] p = { 15, 30, 10 };
            // Make 3x3 and 1x4.
            System.out.println(clothCutting(X, Y, a, b, p));
        }
    }
}