27885번 - 가희와 열리지 않는 건널목

건널목이란, 철로와 도로의 교차점을 말합니다. 열차가 건널목을 지나갈 때, 차나 사람이 지나가지 못하도록 차단기가 내려갑니다.

건널목 중에서는 열차가 자주 지나가서 잘 열리지 않는 건널목이 있습니다. 대표적으로 서울역 근처에 있는 서소문 건널목과 게이큐 본선에 있는 시나가와 건널목이 있습니다.

가희가 살고 있는 동네에는 산성대로 건널목이 하나 있습니다. 산성대로 건널목은 복선으로 이루어진 노선이 하나 지나가며, 상행 열차와 하행 열차가 접근할 수 있습니다. 이 건널목의 동작 방식은 아래와 같습니다.

• 산성대로 건널목을 통과하고 있는 열차가 없으면 차단기가 올라갑니다. 그렇지 않으면 차단기가 내려갑니다.
• 열차가 산성대로 건널목에 접근하면, 40초 후에 완전히 빠져나갑니다. 예를 들어, 열차가 11시 10분 15초에 산성대로 건널목에 접근한 경우
  • 11시 10분 15초부터 11시 10분 55초가 될 때까지 열차는 산성대로 건널목을 통과하게 됩니다.
  • 11시 10분 55초가 되었을 때, 완전히 빠져나갑니다.

하루 동안 상행 열차와 하행 열차가 산성대로 건널목에 접근하는 시각이 주어졌을 때, 몇 초 동안 산성대로 건널목의 차단기가 올라가는지 구해주세요.

첫 번째 줄에 상행 열차 수 c와 하행 열차 수 h가 주어집니다.

다음 c개의 줄에 상행 열차가 산성대로 건널목에 접근한 시각이 hh:mm:ss 형식으로 주어집니다. 먼저 접근한 순서대로 주어집니다.

다음 h개의 줄에 하행 열차가 산성대로 건널목에 접근한 시각이 hh:mm:ss 형식으로 주어집니다. 먼저 접근한 순서대로 주어집니다.

문제에 대한 답을 구해주세요.

• 1 ≤ c ≤ 600
• 1 ≤ h ≤ 600
• 같은 방향의 열차 간격은 60초 이상입니다.
• 주어진 열차 외에 다른 열차가 산성대로 건널목에 접근하지 않습니다.
• 같은 방향으로 향하는 모든 열차는 같은 선로를 사용합니다.
• 두 열차의 방향이 다르다면, 다른 선로를 사용합니다.
• 문제에서 주어지는 모든 시각은 05시 00분 00초 이후이고, 23시 59분 01초 이전입니다.
• 윤초는 무시합니다.

• 복선이란, 2개의 궤도로 구성되어 있는 선로를 말합니다. 문제에서의 복선은 상행, 하행으로 이루어져 있는 선로를 의미합니다.