Nhân dịp ngày lễ quốc tế FA, nhà vua xứ Bedao muốn thúc đẩy chỉ số hạnh phúc của quốc gia nên đã tổ chức một sự kiện ghép đôi thú vị. Có ~n~ người ế lâu năm, nổi tiếng khắp mạng xã hội đã được mời tham gia (trong đó có kazamahoang).

Bản đồ quốc gia có thể quy về hệ tọa độ ~Oxy~, trong đó người thứ ~i~ đang đứng ở vị trí ~(x_i, y_i)~. Trong một đơn vị thời gian, người đứng ở vị trí ~(u, v)~ có thể di chuyển đến các vị trí ~(u + 1, v - 1)~, ~(u + 1, v)~, ~(u + 1, v + 1)~, ~(u, v + 1)~, ~(u - 1, v + 1)~, ~(u - 1, v)~, ~(u - 1, v - 1)~, ~(u, v - 1)~. Để được phát người yêu, tất cả người chơi phải di chuyển đến nơi tổ chức sự kiện đặt ở vị trí ~(a, b)~. Vì tất cả mọi người đều rất nôn nóng có gấu để ôm, mỗi người sẽ di chuyển theo lộ trình nhanh nhất đến nơi tổ chức sự kiện.

Tuy nhiên, đất nước này có ~m~ vùng đất bị nguyền rủa, vùng đất thứ ~j~ sẽ bao phủ một hình chữ nhật có tọa độ góc trái dưới ~(c_j, d_j)~ và tọa độ góc phải trên ~(e_j, f_j)~. Theo truyền thuyết, tất cả các cặp đôi yêu nhau khi đến đây đều không có kết cục tốt đẹp (tất nhiên, lời nguyền này không ảnh hưởng đến những người ế, vì vậy những người tham gia sự kiện có thể đi qua vùng đất này một cách bình thường). Vì thế, nhà vua không muốn tổ chức sự kiện trong những vùng đất này.

Nhà vua muốn chọn vị trí tổ chức sự kiện ~(a, b)~ sao cho thời điểm đầu tiên mà tất cả ~n~ người tập trung là sớm nhất. Hãy giúp nhà vua nhé!

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(n \le 10^5, m \le 5 \cdot 10^4)~ - số người tham gia sự kiện và số vùng đất bị nguyền rủa.

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm hai số nguyên ~x_i, y_i~ (~0 \le x_i, y_i \le 10^9~) - toạ độ hiện tại của người thứ ~i~.

• Dòng thứ ~j~ trong ~m~ dòng tiếp theo chứa bốn số nguyên ~c_j, d_j, e_j, f_j~ (~0 \le c_j \le e_j \le 10^9, 0 \le d_j \le f_j \le 10^9~) - toạ độ góc trái dưới và phải trên của vùng đất nguyền rủa thứ ~j~.

Output

• In ra thời điểm sớm nhất mà sự kiện có thể bắt đầu.

Scoring

• ~10\%~ số test thoả mãn ~m = 1~.

• ~20\%~ số test khác thoả mãn ~m \le 18~.

• ~20\%~ số test khác thoả mãn ~m \le 300~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

2 4
3 3
2 2
1 1 4 4
4 3 4 5
3 4 5 5
1 3 4 4

Sample Output 1

3

Notes