EIU Programming Practices and Exams

Anh Beo và anh Phúc đang làm trong dự án phần mềm tư vấn du lịch xuyên Việt. Chức năng Beo và Phúc đang làm hoạt động như sau: trên hành trình xuyên Việt, tại mỗi địa phương chương trình sẽ đề xuất cho khách hàng một địa điểm được bình chọn cao nhất bởi những khách du lịch đã từng tham quan. Chương trình đang được xây dựng nên không có số liệu thực để kiểm tra. Bên cạnh đó chương trình đòi hỏi tốc độ xử lý nhanh, có thể đáp ứng nhu cầu sử dụng của nhiều khách hàng đồng thời. Anh Phúc đã thiết kế một dạng test cases đặc biệt để kiểm tra. Em hãy viết chương trình để thách thức anh Beo xem chương trình của ai sẽ hoàn thành những test cases của anh Phúc.

Input

Dòng đầu tiên là số nguyên N (1 ≤ N ≤ 10⁶) số địa phương trên hành trình.

Dòng thứ i, trong N dòng tiếp theo, gồm số nguyên N_i (0 ≤ N_i ≤ 10⁶) là số địa điểm ở địa phương thứ i, và hai số nguyên A_i và B_i (0 < A_i, B_i ≤ 10⁹) được sử dụng để tính bình chọn tại N_i địa điểm như sau: n_i1 = A_i % B_i, n_ij = (n_i(j-1) * A_i) % B_i với 1 < j ≤ N_i.

Dữ liệu đảm bảo

Output

In ra tổng số bình chọn lớn nhất của các địa điểm mà chương trình đề xuất.

Example