전역 역전 | cho.sh

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

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

조기 전역: 모아놓은 휴가를 말년에 전역일을 앞당기는 데 사용할 수 있다.
군기교육대: 징계를 받아 군기교육대에 가게 되면, 군기교육대에 있던 기간만큼 전역이 늦춰진다.
임기제 부사관: 임기제 부사관에 지원하여 $6$개월에서 $48$개월까지 전문하사로 부대에 남아 국가 안보에 조금 더 이바지할 수 있다. 임기제 부사관 지원서에서의 $1$개월은 $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일이다.