1042 : Mafia
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

พื้นที่แห่งหนึ่งมีกลุ่มมาเฟียที่มีอิทธิพลอยู่เป็นจำนวนมาก กำหนดให้ขอบเขตอิทธิพลของมาเฟียทุกกลุ่มมีลักษณะเป็นวงกลม โดยมาเฟียสองกลุ่มใดๆ สามารถมีขอบเขตอิทธิพลซ้อนทับกันบางส่วนหรือทั้งหมดหรือไม่ซ้อนทับกันเลยก็ได้ ทางรัฐบาลต้องการทำลายเขตอิทธิพลของมาเฟียเหล่านี้ให้ได้มากที่สุด จึงได้จัดตั้งตำรวจกองหนึ่งเพื่อคอยตรวจตราถนนสายต่างๆ ภายในเมือง แต่ทว่าวันนี้มีตำรวจเหลือเพียงนายเดียวเท่านั้น จึงต้องการให้คุณช่วยหาว่าตำรวจนายนี้จะเดินตรวจบนถนนสายใดเพื่อให้เดินผ่านเขตอิทธิพลให้ได้มากที่สุด โดยตำรวจจะเป็นเป็นเส้นตรงที่ขนานแกน x หรือแกน y เท่านั้น และการเดินผ่านขอบเขตอิทธิพลหมายถึงการที่เส้นทางนั้นตัดผ่านขอบเขตอิทธิพลหรือสัมผัสวงกลมขอบเขตอิทธิพลก็ได้

โจทย์
เมืองแห่งหนึ่งมีลักษณะเป็นสี่เหลี่ยมผืนผ้าขนาดกว้าง N หน่วยยาว M หน่วย และมีกลุ่มมาเฟียที่มีอิทธิพลทั้งหมด K กลุ่ม โดยแต่ละกลุ่มจะมีเขตอิทธิพลเป็นของตัวเองซึ่งอาจซ้อนทับกับกลุ่มอื่นได้ หน้าที่ของคุณคือหาถนนที่ดีที่สุดสำหรับตำรวจหนึ่งนายในการเดินตรวจตรา คือถนนดังกล่าวจะต้องผ่านเขตอิทธิพลของมาเฟียให้มากกลุ่มที่สุดเท่าที่จะทำได้

ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม 3 จำนวนคือ N, M ที่แทนขอบเขตของพื้นที่ทั้งหมด (1 ≤ N, M ≤ 5000) และ K  แทนจำนวนกลุ่มมาเฟียทั้งหมดที่มีภายในเมือง (1 ≤ K ≤ 10000)
ต่อมาอีก K บรรทัดจะเป็นข้อมูลเขตอิทธิพลของมาเฟียแต่ละกลุ่ม โดยในบรรทัดที่ 1+I จะเป็นข้อมูลของมาเฟียกลุ่มที่ I และในแต่ละบรรทัดจะรับจำนวนเต็มสามจำนวนได้แก่ พิกัดตำแหน่งจุดศูนย์กลางของวงกลมอิทธิพล X, Y ที่มีค่าเป็นจำนวนเต็ม (0 ≤ X ≤ N และ 0 ≤ Y ≤ M) และจำนวนเต็ม R แทนรัศมีของวงกลม (1 ≤ R ≤ 100)

ข้อมูลส่งออก
ให้ตอบเพียงบรรทัดเดียว ที่แสดงจำนวนวงกลมที่ตัดได้มากที่สุด เมื่อลากเส้นขนานกับแกน x หรือแกน y

ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2550

รูปประกอบตัวอย่างข้อมูลนำเข้า

จากตัวอย่างสามารถวาดวงกลมได้ดังรูป และเมื่อลากเส้นขนานแกน x
ที่ตำแหน่งความสูง y = 6 เส้นตรงนี้จะผ่านวงกลมทั้งหมด 5 วง

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
10 10 6 2 4 2 2 5 1 5 7 3 6 9 1 9 7 1 7 3 3	5

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้