Under construction

Still being built. Things may change

Another Brick in the Wall

Time limit2sMemory limit2048 MB

Summary
Find the fewest 1 x 3 bricks needed to build an l by h wall from 1 x 2 and 1 x 3 bricks so that no two seams line up vertically.
Level

Medium7 of 10

Topics
Dynamic programming, Bit manipulation
Solved
No attempts yet

Problem

Alice likes building toy walls. She has many 1×21 \times 2 bricks and a limited supply of 1×31 \times 3 bricks. Both types of bricks are 1 unit high and cannot be rotated.

Alice builds a wall one unit thick, with length ll and height hh, using these bricks. A wall is solid if no seam lies directly above another seam.

Good seam placementBad seam placementSolid 7×47 \times 4 wall

Find the minimum number of 1×31 \times 3 bricks needed to build a solid wall of length ll and height hh.

Input

The only line contains two integers ll and hh, the length and the height of the wall (5≤l≤10005 \le l \le 1000; 2≤h≤10002 \le h \le 1000).

Output

Print the minimum number of 1×31 \times 3 bricks needed to build a solid l×hl \times h wall.

It is always possible to build a solid wall of length ll and height hh.

Examples1

  1. Example 1

    Input
    7 4
    
    Expected output
    4