전역 역전

시간 제한1초메모리 제한1024 MB

요약

주어진 여유 시간 안에서 행동을 골라 영도가 종현보다 먼저 전역하는 날수를 최대로 하고, 불가능하면 늦는 날수를 최소로 합니다.

문제

영도는 국방의 의무를 다하기 위해 대한민국 육군에 입대했다. 고된 훈련병 생활과 후반기 교육을 마치고 자대 배치를 받고 나니, 자대에는 먼저 입대한 친구 종현이 있었다.

영도는 종현이 먼저 전역하는 것이 마음에 들지 않았다. 그래서 아래의 제도와 규정을 활용해 종현보다 먼저 전역할 계획을 세웠다.

조기 전역: 모아 둔 휴가를 말년에 전역일을 앞당기는 데 사용할 수 있다.
군기교육대: 징계를 받아 군기교육대에 가게 되면, 군기교육대에 있던 기간만큼 전역이 늦춰진다.
임기제 부사관: 임기제 부사관에 지원하면 $6$ $6$ 개월에서 $48$ $48$ 개월까지 전문하사로 부대에 남아 국가 안보에 조금 더 이바지할 수 있다. 임기제 부사관 지원서에서 $1$ $1$ 개월은 $30$ $30$ 일로 계산한다.
- 영도와 종현의 부대는 인력이 부족해서, 임기제 부사관 지원서를 여러 장 중복해서 제출할 수 있다. 이때 복무 기간은 기간 제한의 영향을 받지 않고 누적된다. 만약 $48$ 개월 전문하사 지원서를 두 장 작성해 제출한다면 $96$ 개월을 복무하게 된다.

영도는 이 제도와 규정을 적절히 활용해 영도의 전역일을 앞당기거나 종현의 전역일을 늦추려고 한다. 계획이 남에게 들키면 오히려 본인의 전역일이 늦춰질 수 있으므로, 영도는 계획을 몰래 실행할 수 있는 여유 안에서만 계획을 이어 가려고 한다.

모아 둔 휴가를 모두 사용해도 영도의 전역일은 입대일을 넘어서지 않는다고 가정한다. 영도는 얻을 수 있는 최대 휴가로 조기 전역을 하더라도 계획을 세우는 날 이후에 전역한다.

종현의 전역 예정일이 $Y_1$ 년 $M_1$ 월 $D_1$ 일일 때, 첫 번째 줄에 세 수 $Y_1$ , $M_1$ , $D_1$ 이 YYYY MM DD 형식으로 주어진다.

영도의 전역 예정일이 $Y_2$ 년 $M_2$ 월 $D_2$ 일일 때, 두 번째 줄에 세 수 $Y_2$ , $M_2$ , $D_2$ 가 YYYY MM DD 형식으로 주어진다.

세 번째 줄에 영도가 계획을 실행하는 데 사용할 수 있는 여유 $T$ 와 계획을 위해 할 수 있는 행동의 개수 $N$ 이 공백으로 구분되어 주어진다.

네 번째 줄부터 $N$ 개의 줄에 걸쳐 계획을 위해 할 수 있는 행동이 주어진다. 각 행동은 최대 한 번 할 수 있다.

$1$ $C$ $V$ : 영도가 $C$ 만큼의 여유를 투자해서 휴가 $V$ 일을 받아낸다. 영도가 얻은 휴가는 이후 자신의 조기 전역에 사용한다.
$2$ $C$ $G$ : 영도가 $C$ 만큼의 여유를 투자해서 거대한 음모를 세운다. 종현은 음모에 휘말려 징계를 받고 $G$ 일 동안 군기교육대에 다녀온다.
$3$ $C$ $M$ : 영도가 $C$ 만큼의 여유를 투자해서 종현의 $M$ 개월 임기제 부사관 지원서를 대신 작성한다.

두 사람의 전역일은 입력으로 주어진 영도의 행동 외에 다른 요인으로는 변하지 않는다. 주어지는 수는 모두 정수이다.

영도가 종현보다 먼저 전역할 수 있다면, 영도가 종현보다 먼저 전역하게 되는 날의 수의 최댓값을 출력한다.

영도가 종현보다 먼저 전역할 수 없다면, 영도가 종현보다 늦게 전역하게 되는 날의 수의 최솟값을 출력한다.

윤년은 100의 배수가 아닌 4의 배수이거나, 400의 배수인 해이다. 윤년에는 2월 29일이 존재하므로 한 해가 366일이다.

예제 1

입력

예상 출력

예제 2

입력

예상 출력