Trên trục số cho 𝑛 khoảng đóng, khoảng thứ 𝑖 là [𝑎𝑖 , 𝑏𝑖 ] được định nghĩa bởi:
[𝑎𝑖 , 𝑏𝑖 ] = {𝑥|𝑎𝑖 ≤ 𝑥 ≤ 𝑏𝑖 } . Hãy chọn trên trục số một số ít nhất các điểm nguyên phân biệt sao cho có ít nhất 𝑐𝑖 điểm được chọn thuộc vào đoạn thứ 𝑖.

Input

Dòng 1 chứa số nguyên dương 𝑛 ≤ 100000

𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa ba số nguyên 𝑎𝑖 , 𝑏𝑖 , 𝑐𝑖 (−10^18 ≤ 𝑎𝑖 ≤ 𝑏𝑖 ≤ 10^18; 𝑐𝑖 ≤ 𝑏𝑖 − 𝑎𝑖 + 1)

Output

Ghi số nguyên duy nhất là số điểm nguyên được chọn theo phương án tìm được

Sample Input

3 
1 5 1 
4 7 4 
2 8 5

Sample Output

5