Description

You are given a rectangular board with width w and height h. The board may be cut repeatedly along horizontal or vertical directions. Each resulting rectangle can also be further cut in the same way.

However, rectangles can only be sold if they match one of exactly three allowed sizes, specified as:

• w1 × h1

• w2 × h2

• w3 × h3

Because the board has grain texture, rectangles cannot be rotated. (有方向性)
The selling price of a rectangle is:

• price = width × height

Your task is to compute the maximum total selling price obtainable by cutting the original w×h board into zero or more allowed rectangles. Cutting may produce leftover rectangles that cannot be sold; such pieces contribute zero profit.

 

Sample Input / Output

A 5×7 board can be cut into two 5×2 pieces and two 2×3 pieces.
The total value obtained is:

• 5×2 + 5×2 + 2×3 + 2×3 = 32

Hint

Instead of directly computing the maximum sellable area, we can compute the minimum wasted area during cutting. Here is some pseudocode that you can refer to.

constant N_PIECE = 3      # we have 3 sellable sizes

# sellable sizes are stored as:
# size[i].w = width of piece i
# size[i].h = height of piece i

function min_piece(w, h, size[0..N_PIECE-1]) -> int

    # 1. invalid size: no waste
    if w <= 0 OR h <= 0 then
        return 0
    end if

    # 2. if this rectangle exactly matches a sellable size,
    #    we can sell it completely → no waste
    for i from 0 to N_PIECE-1 do
        if w == size[i].w AND h == size[i].h then
            return 0
        end if
    end for

    # 3. check whether we can at least cut out one sellable piece inside
    canCut := false
    for i from 0 to N_PIECE-1 do
        if w >= size[i].w AND h >= size[i].h then
            canCut := true
        end if
    end for

    # if we cannot cut out any of the 3 sellable sizes,
    # then the whole w×h area is wasted
    if canCut == false then
        return w * h
    end if

    # 4. try cutting using each sellable size as a "reference" piece
    minWaste := w * h     # initialize with worst case

    for i from 0 to N_PIECE-1 do

        wi := size[i].w
        hi := size[i].h

        # only consider this size if it fits inside w×h
        if w >= wi AND h >= hi then

            # --- Cut style 1: cut horizontally first ---
            #   top:    w × (h - hi)
            #   bottom: (w - wi) × hi
            waste1 := min_piece(w,      h - hi, size)
                      + min_piece(w - wi, hi,    size)

            if waste1 < minWaste then
                minWaste := waste1
            end if

            # --- Cut style 2: cut vertically first ---
            #   left:   (w - wi) × h
            #   right:  wi × (h - hi)
            waste2 := min_piece(w - wi, h,      size)
                      + min_piece(wi,    h - hi, size)

            if waste2 < minWaste then
                minWaste := waste2
            end if

        end if
    end for

    return minWaste
end function

Input

First line: two integers w, h — width and height of the original board.

Next three lines: each line contains two integers describing one allowed rectangle size:

• w1, h1
• w2, h2
• w3, h3

Constraints:

• 0 < w, h ≤ 32

• 0 < w1, w2, w3 ≤ w

• 0 < h1, h2, h3 ≤ h

Output

A single integer: the maximum total profit achievable by cutting and selling rectangles according to the rules.

The output must exactly match the required format.

Sample Input  Download

Sample Output  Download

Tags

Discuss