치즈를 부탁해요

"We Cut The Cheese"라는 전문 식품점에서는 여러 가지 치즈 블렌드를 판매한다. 예를 들어 이탈리안 블렌드는 프로볼로네 50%, 모차렐라 30%, 파르메산 20%로 만들고, 아프리칸 사파리는 도미아티 74%, 아리시 25%, 보크마키리를 아주 약간(1%) 넣어 만든다. 당신은 치즈 블렌드 시식 담당으로 이 가게에서 일하기 시작했지만, 2년이 지나고 몸무게가 45파운드 늘어난 끝에 회계 부서장까지 올라갔다. 이 가게는 계절, 시장 가격, 그 밖의 요인에 따라 매주 다양한 치즈를 납품받는다. 이렇게 들어온 치즈의 양과 각 치즈 블렌드에 필요한 비율이 주어질 때, 당신은 매주 이 치즈를 최적으로 사용해 이익을 최대화하는 방법을 결정해야 한다. 가게가 몇 가지 치즈 블렌드만 만들던 시절에는 손으로 계산할 수 있었지만, 사업이 치즈 수플레보다 빠르게 커지면서 블렌드의 수도 늘어나 이제는 프로그램으로 최적의 치즈 사용법을 구해야 하는 상황이다. 그래서 묻겠다. 당신은 이런 프로그램을 작성할 만큼 gouda-nough한가?

입력의 첫 줄에는 두 양의 정수 n m (1 ≤ n, m ≤ 50)이 주어진다. n은 치즈 블렌드를 만드는 데 쓰이는 치즈의 종류 수이고, m은 가게에서 판매하는 서로 다른 치즈 블렌드의 수이다. 다음 줄에는 n개의 정수 w1 w2 . . . wn (0 ≤ wi ≤ 500)이 주어지는데, wi는 가게가 보유한 치즈 i의 파운드 수이다. 그다음 m개의 줄이 p1 p2 p3 . . . pn t (0.0 ≤ pi ≤ 100.0, 0.0 ≤ t ≤ 10.0) 형태로 주어진다. pi는 블렌드에 들어가는 치즈 i의 비율을 나타내고, t는 그 블렌드의 파운드당 이익이다.

주어진 치즈의 양, 블렌드 비율, 이익이 주어졌을 때, 만든 블렌드가 전부 팔린다고 가정하고 얻을 수 있는 최대 이익을 출력한다. 답은 소수점 아래 두 자리로 반올림한다.