[L] LCG Madness!

메모리 제한에 유의하라.

바이히는 최근 하이비가 만든 두뇌 게임 LCG Madness!를 플레이하고 있다. 이 게임의 규칙은 다음과 같다.

1. $N$개의 LCG 기계가 주어진다. 각 기계에는 정수 $X_i$를 보여주는 모니터와, 앞면과 뒷면을 가진 뒤집을 수 있는 카드, 그리고 기계 내부에 저장된 $4$개의 정수 $A_i$, $B_i$, $I_i$, $M_i$가 있다.

2. 게임이 시작될 때, 모든 기계에 대해 $X_i=I_i$로 초기화된다.

3. 그리고 플레이어는 각각의 기계에 대해 카드를 앞면 또는 뒷면이 보이도록 원하는 대로 뒤집는다.

4. 이후 $R$번의 라운드에 걸쳐 아래 과정을 반복한다.

   • 모든 LCG 기계를 $1$회 실행한다. 구체적으로는 모든 기계에 대해 $X_i$를 $(A_i\cdot X_i+B_i)\bmod M_i$로 바꾼다. 여기서 $a\bmod b$는 $a$를 $b$로 나눈 나머지를 의미한다.
   • 이후 플레이어는 $N$개의 기계 중 하나를 선택한 뒤, 해당 기계의 카드를 뒤집는다.
   • 이후 플레이어는 방금 뒤집은 카드를 포함해서, 방금 뒤집은 카드와 같은 면을 보이는 카드를 가지는 기계들에 적힌 $X_i$의 합만큼 점수를 얻는다.

바이히는 이 게임을 자주 플레이하다 보니, 플레이할 때마다 최고점을 찍는 경지에 이르렀다. 이를 하이비한테 증명하기 위해, 바이히는 게임의 초기 상태가 주어질 때 최고점을 계산해 주는 프로그램을 작성해서 보여주기로 했다.

첫째 줄에는 LCG 기계의 개수 $N$과 플레이하는 라운드의 수 $R$이 공백으로 구분되어 주어진다. $(1\le N\le 10;$ $1\le R\le 17\, 012)$

둘째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에는 LCG 기계에 저장되는 $4$개의 정수 $A_i$, $B_i$, $I_i$, $M_i$가 공백으로 구분되어 주어진다. $(0 \le A_i,B_i,I_i \lt M_i \le 10^9)$

첫째 줄에 바이히가 얻을 수 있는 최고 점수를 출력한다.