문제

최근 LIBe는 월드 오브 워크래프트라는 게임에 푹 빠져있다. 친구의 말에 따르면 최근에는 vim을 켜서 노는 시간 보다, 비룡을 타고 노스랜드를 거닐고 있는 시간이 많다고 한다. 게임에서 LIBe가 조종하는 캐릭터의 직업은 도적이다. 도적은 강력한 공격력으로 알려져 있지만, 최대 레벨인 80 전까지는 다수의 적의 공격을 받게되면 광역 공격 (한번에 다수를 때릴 수 있는 공격) 이 없어서 순식간에 죽어버리기 일쑤였다. 천신만고 끝에 LIBe는 캐릭터의 레벨을 80 레벨까지 올렸고, 궁극의 기술인 칼날 부채를 얻게 되었다. 칼날 부채란 일정 반경의 모든 적들에게 공격을 하는 기술이다. 칼날 부채를 습득해서 신이 난 LIBe는 위력을 시험해보기 위해서 LIBe는 오그리마에 있는 명예의 골짜기로 가서 데미지의 양을 시험해보기로 하였다.

시험을 하기 위한 필드는 H*W 의 격자 형태로 이뤄져 있고, 여기에 여러 개의 허수아비와 장애물들이 흩어져 있다. LIBe의 캐릭터는 필드의 맨 왼쪽 위 칸에서 시작하며, 매 1초마다 이동, 대기, 그리고 칼날 부채 시전 동작 중 하나를 할 수 있다.

• 이동할 경우, 상하좌우 방향으로 최대 1칸 움직일 수 있다. 단, 필드 밖이나 장애물이 있는 칸으로는 이동이 불가능하다.
• 대기할 경우, 현재 위치에서 1초간 기다린다.
• 칼날 부채를 시전하면 현재 위치에서 맨하탄 거리 L 이하에 있는 모든 허수아비를 한 번에 공격한다. 칼날 부채의 공격력은 A 인데, 각 허수아비가 받는 데미지는 max(0,A-(해당 허수아비의 방어력)) 이 된다. 허수아비는 무한대의 체력을 갖고 있어서 아무리 맞아도 쓰러지지 않으며, 칼날 부채는 장애물을 무시하고 공격할 수 있다.
• 칼날 부채는 한번 시전한 이후 CT 초 동안은 기술을 사용할 수 없다. 예를 들어, CT=1 이라면 한번 기술을 쓴 후에는 1초간 대기하거나 이동해야 다음 기술을 쓸 수 있다.

이와 같은 제한 조건 하에서 TL 초동안 필드를 돌아다니며 칼날 부채를 시전해 낼 수 있는 최대 데미지 양을 계산하는 프로그램을 작성하라.