소매치기

경찰서는 Jewellery Stores 골목의 맨 위쪽에 있다. 이 위치는 마을 소매치기 업계에서 아주 중요하다. 경찰은 매일 골목 위쪽 끝에서 순찰을 시작해 천천히 아래로 내려갔다가 다시 위로 돌아가며, 낮 동안 골목 아래쪽 끝까지 가는 일은 드물다. 경찰의 습관에는 규칙성이 많아서, Big Pickpocket Boss(BPB)는 휴일을 위한 계획을 세울 수 있다. 골목의 가게에는 골목 아래에서 위쪽으로 1부터 시작하는 연속된 정수가 붙어 있다. 휴일의 각 날짜마다 BPB는 처음부터 특정 라벨까지의 가게들이 경찰의 감시에서 벗어나 안전하다고 보장할 수 있다. 소매치기 팀들이 BPB를 위해 일을 처리한다. 사용할 수 있는 팀은 많고, 각 팀은 한 가게에서 연속된 며칠 동안만 일할 수 있다. 모든 팀을 반드시 고용할 필요는 없다.

BPB는 무서운 보스이고, 그의 규칙은 철저히 지켜야 한다.

• 가게가 안전한 날에는 그 가게에서 정확히 한 팀이 일한다.
• 팀이 어떤 가게에서 일을 시작하면, 그 가게에서 연속된 며칠 동안 일한다.
• 어떤 날에 가게가 안전하지 않다면, 그 날 그 가게에서는 아무 팀도 일하지 않는다.
• 어떤 팀도 두 개 이상의 가게에서 일하지 않는다.
• 어떤 팀도 휴일 동안 두 번 이상 일하지 않는다.
• 어떤 팀도 휴일 전이나 후에 일하지 않는다.

각 팀은 자기 일이 진행되는 전체 기간 동안 BPB에게 특정한 최소 수입을 벌어들인다고 알려져 있다. BPB는 자신의 최소 총수입을 최대화해야 한다는 것을 안다. 그는 오늘 오후 3시까지, 그보다 늦지 않게 그 값을 원한다. 그를 실망시키려고 하지 마라.

첫째 줄에는 두 정수 H와 T(1 ≤ H ≤ 105, 1 ≤ T ≤ 16)가 주어진다. H는 휴일의 일수, T는 사용할 수 있는 팀의 수이다. 둘째 줄에는 H개의 정수 Ck(0 ≤ Ck ≤ 105, 1 ≤ k ≤ H)가 주어지며, 휴일 k일째에 안전한 가게의 최고 라벨을 나타낸다. 라벨 0은 휴일 k일째에 안전한 가게가 없음을 뜻한다. 다음 T개의 줄 각각에는 두 정수 Dt와 It(1 ≤ Dt ≤ H, 0 ≤ It ≤ 106, 1 ≤ t ≤ T)가 주어지며, 팀 t의 일수와 팀이 벌어들이는 최소 수입을 나타낸다.

팀들을 적절히 배치했을 때 팀들이 벌어들일 수 있는 최소 총수입의 최댓값을 출력한다. BPB의 조건을 만족시킬 수 없으면 0을 출력한다.