도토리 숨기기

수형이는 HEPC 1등 상금으로 도토리 $D$개를 받았다. 다른 다람쥐에게 빼앗기지 않으려고 1번부터 $N$번까지 번호가 붙은 상자 $N$개에 도토리를 전부 숨기기로 했다.

상자가 너무 많아 어느 상자에 넣었는지 다 외울 수 없으니 규칙을 정했다. 세 수 $A$, $B$, $C$로 이루어진 규칙 하나는 $A$번, $A+C$번, $A+2C$번 상자처럼 $C$칸씩 건너뛰며 $B$번을 넘지 않는 상자마다 도토리를 하나씩 넣으라는 뜻이다. 규칙 하나가 들통나 도토리를 전부 잃는 것이 두려워 이런 규칙을 $K$개 만들었다.

예를 들어 100번 상자부터 150번 상자까지 10칸 간격으로 넣는 규칙과 110번 상자부터 150번 상자까지 15칸 간격으로 넣는 규칙을 만들면 도토리가 들어가는 상자는 100, 110, 120, 125, 130, 140, 150번이고 110번과 140번 상자에는 도토리가 2개씩 들어간다.

한 상자에 들어가는 도토리 개수에는 제한이 없다. 규칙이 지정한 자리를 상자 번호가 작은 쪽부터 차례로 하나씩 채워 도토리 $D$개를 모두 넣었을 때, 마지막 도토리가 들어간 상자의 번호를 출력하는 프로그램을 작성하시오.

첫째 줄에 상자의 개수 $N$, 규칙의 개수 $K$, 도토리의 개수 $D$가 공백으로 구분되어 주어진다. ($1 \le N \le 1{,}000{,}000$, $1 \le K \le 10{,}000$, $1 \le D \le 1{,}000{,}000{,}000$)

다음 $K$개의 줄에는 줄마다 규칙을 나타내는 세 정수 $A$, $B$, $C$가 공백으로 구분되어 주어진다. ($1 \le C \le A \le B \le N$)

$D$는 모든 규칙이 지정하는 자리의 총 개수보다 작거나 같다.

첫째 줄에 마지막 도토리가 들어간 상자의 번호를 출력한다.