대형 스크린

상근이는 작은 모니터 여러 개를 격자 모양으로 이어 붙여 하나의 대형 모니터를 만든다.

고객은 원하는 대형 모니터의 가로·세로 해상도(픽셀)와 가로·세로 크기(밀리미터)를 알려 준다. 상근이는 고객이 요구한 값보다 가로·세로 해상도가 모두 크거나 같고, 가로·세로 크기도 모두 크거나 같은 대형 모니터를 만들어야 한다. 이때 드는 제조 비용을 최소로 하려고 한다.

하나의 대형 모니터는 반드시 같은 종류의 모니터만으로 만들어야 한다. 작은 모니터를 가로로 $a$개, 세로로 $b$개인 $a \times b$ 격자로 이어 붙이면, 대형 모니터의 가로 해상도와 가로 크기는 가로로 이어 붙인 개수만큼, 세로 해상도와 세로 크기는 세로로 이어 붙인 개수만큼 각각 더해진다. 비용은 사용한 모니터 가격의 총합, 즉 (모니터 개수) $\times$ (모니터 한 대 가격)이다.

창고에는 여러 종류의 모니터가 있으며, 각 종류의 해상도·크기·가격을 모두 알고 있다. 모니터는 90도 회전시켜 사용할 수 있는데, 회전하면 가로와 세로가 서로 바뀐다. 다만 하나의 대형 모니터에 들어가는 모니터는 모두 같은 방향이어야 한다. 각 종류의 모니터는 필요한 만큼 얼마든지 사용할 수 있다.

가능한 가장 저렴한 제조 비용을 구하여라.

첫째 줄에 대형 모니터의 가로 해상도, 세로 해상도, 가로 크기, 세로 크기를 나타내는 정수 $r_h$, $r_v$, $s_h$, $s_v$가 공백으로 구분되어 주어진다. 각 값은 $100$ 이상 $10{,}000$ 이하이다.

둘째 줄에 상근이가 가지고 있는 모니터 종류의 개수 $n$이 주어진다. ($1 \le n \le 100$)

이어지는 $n$개의 줄에는 각 모니터 종류의 가로 해상도, 세로 해상도, 가로 크기, 세로 크기, 가격을 나타내는 정수 $r_{h,i}$, $r_{v,i}$, $s_{h,i}$, $s_{v,i}$, $p_i$가 주어진다. 이 값들도 모두 $100$ 이상 $10{,}000$ 이하이다.

대형 모니터를 만드는 데 드는 가장 저렴한 제조 비용을 첫째 줄에 출력한다.