Another Brick in the Wall

시간 제한2초메모리 제한2048 MB

요약
1×2와 1×3 벽돌로 l×h 벽을 쌓되 이음선이 바로 위아래로 겹치지 않게 할 때 필요한 1×3 벽돌의 최소 개수를 구한다.
난이도

보통10점 중 6점

유형
동적 계획법, 조합론, 수학
정답자
아직 제출이 없습니다

문제

Alice likes building toy walls. She has a lot of 1×21 \times 2 bricks and a limited supply of 1×31 \times 3 bricks. Both types of bricks have a height of 1 and can not be rotated.

Alice is going to build a one unit thick wall of length ll and height hh out of these bricks. A wall is solid if there are no seams directly above another seam.

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

Help Alice determine the minimum number of 1×31 \times 3 bricks required to build a solid wall of length ll and height hh.

입력

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

출력

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

It can be shown that it is always possible to build a solid wall of length ll and height hh.

예제1

  1. 예제 1

    입력
    7 4
    
    예상 출력
    4