조기 시험 대피

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

요약

N행 강당에 앉은 M명이 앞문이나 뒷문으로 빠져나갈 때 통과 인원과 방 혼잡에 따른 비용 합을 최소화합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

N행짜리 좁은 강당에서 시험을 봅니다. 각 행에는 A부터 F까지 6석이 있고 통로는 C와 D 사이입니다. 앞과 뒤에 안전실이 있습니다. M명이 순서대로 퇴장하며, 각자 앞 또는 뒤 안전실을 선택합니다. 불편함은 Ax+By이며, x는 이동 중 지나친 사람 수, y는 이미 그 안전실에 있는 사람 수입니다. 총 불편함을 최소화하세요.

입력

첫 줄에 N, M, A, B가 있습니다. 다음 M줄에 Ri와 Ci가 주어집니다.

출력

M명의 최소 총 불편함을 출력합니다.

예제2

예제 1
입력
```
5 5 3 4
3E
1D
5C
1E
4A
```
예상 출력
```
55
```
예제 2
입력
```
1 1 2 3
1A
```
예상 출력
```
6
```