베이커리

Bessie는 베이커리를 열었다. 이 베이커리의 오븐은 쿠키 하나를 $t\_C$ 단위 시간에, 머핀 하나를 $t\_M$ 단위 시간에 만들 수 있다($1\le t\_C,t\_M\le 10^9$). 공간이 부족해서 Bessie는 한 번에 페이스트리 하나만 만들 수 있다. 따라서 쿠키 $A$개와 머핀 $B$개를 만드는 데 $A \cdot t\_C + B \cdot t\_M$ 단위 시간이 걸린다.

Bessie의 친구는 $N$명이다($1\le N\le 100$). 친구들은 한 명씩 차례로 베이커리를 찾는다. $i$번째 친구는 입장하자마자 쿠키 $a\_i$개($1 \leq a\_i\leq 10^9$)와 머핀 $b\_i$개($1 \leq b\_i \leq 10^9$)를 주문한다. 페이스트리를 보관할 공간이 없어서, Bessie는 주문이 들어온 뒤에야 만들기 시작한다. $i$번째 친구는 최대 $c\_i$ 단위 시간($a\_i + b\_i \leq c\_i \leq 2 \cdot 10^{18}$)까지 기다리고, 그 시간이 지나면 속상해서 떠난다.

Bessie는 무니 1개를 써서 오븐을 업그레이드할 수 있다. 업그레이드 한 번에 쿠키 하나를 만드는 시간 또는 머핀 하나를 만드는 시간이 1단위 줄어든다. 업그레이드 횟수는 정수여야 하지만, 친구들이 도착하기 전에 필요한 만큼 업그레이드할 수 있다. 단, 쿠키를 만드는 시간과 머핀을 만드는 시간은 모두 0보다 커야 한다.

모든 친구를 만족시키기 위해 Bessie가 써야 하는 무니의 최소 개수를 구한다.