Bessie vừa mở một tiệm bánh!

Trong tiệm bánh của mình, Bessie có một lò nướng có thể làm một chiếc bánh quy trong \(t_C\) giây hoặc một chiếc bánh nướng xốp trong \(t_M\) giây \((1\leq t_C,t_M\leq10^9)\). Do hạn chế về không gian, Bessie chỉ có thể làm một chiếc bánh ngọt mỗi lần, vì vậy để làm \(A\) bánh quy và \(B\) bánh nướng xốp, phải mất \(A*t_C+B*t_M\) giây.

\(N(1 \leq N \leq 100)\) người bạn của Bessie muốn lần lượt tham quan tiệm bánh. Người bạn thứ \(i\) sẽ gọi \(a_i\) \((1 \leq a_i \leq 19^9)\) bánh quy và \(b_i(1 \leq b_i \leq 10^9)\) bánh nướng xốp ngay khi bước vào. Bessie không có chỗ để đựng bánh ngọt nên nó chỉ bắt đầu làm bánh ngọt khi nhận được đơn đặt hàng. Hơn nữa, bạn bè của Bessie rất bận rộn nên người bạn thứ \(i\) chỉ sẵn lòng đợi $c_i(a_i+b_i