제빵왕 현빈이는 빵집을 열었다.

빵집의 오븐은 한 개의 쿠키를 t_C분동안 만들거나 한개의 머핀을 t_M분 동안 만들 수 있다. (1≤t_C,t_M≤10^9).

공간 제약 때문에 현빈이는 동시에 한 개의 빵만 만들 수 있다. 그래서 A개의 쿠키와 B개의 머핀을 만들려면 A \times t_C + B \times t_M분이 걸린다.

N(1≤N≤100)명의 친구들이 한번에 한 명씩, 현빈이의 빵집에 방문하려고 한다.

i번 친구는 입장 하자마자 a_i(1 \le a_i \le 10^9)개의 쿠키와 b_i (1 \le b_i \le 10^9)개의 머핀를 주문한다.

현빈이가 만든 제품들은 미리 만들어서 보관할 장소가 없기에, 주문이 들어오면 항상 그때 만들어야 한다.

그리고 i번 친구는 c_i(a_i+b_i≤c_i≤2⋅10^{18})분만 기다릴 수 있으며, 그 시간을 초과하면 슬퍼하고 떠난다.

현빈이는 모든 친구들이 슬퍼하지 않도록, 오븐을 업그레이드 하기로 했다. 오븐을 비용 1만큼 사용하여 업그레이드하면 쿠키 만드는 시간이 1분 줄어들거나, 머핀 만드는 시간이 1분 줄어든다.

항상 1분 단위로만 감소하며, 한 개의 빵을 만드는데 걸리는 시간은 최소 단위가 분 단위이며 자연수이다.

T(1≤T≤100)개의 테스트 케이스마다 현빈이가 모든 친구들을 슬퍼하지 않도록 만들 수 있는 최소 업그레이드 비용을 구하라.

빵집 (Bakery) timer 1s memory 256MB

빵집 (Bakery) 1s 256MB