1077 : กุญแจ (key)
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 128 megabyte(s)

                และแล้วคำแนะนำที่ดีเยี่ยมก็โผล่มาดั่งอัศวินขี่ม้าขาว นักเลงคอมพิวเตอร์นิรนามผู้หนึ่งได้ช่วยให้คุณเจาะเข้าไปถึงโครงสร้างข้อมูลซึ่งมีลักษณะเป็นตาราง คุณทราบจากนักเลงคอมพิวเตอร์นิรนามว่ากุญแจสุดท้ายที่จะไขเข้าไปสู่ระบบฐานข้อมูลของ TOI.C อยู่ในกระจายอยู่ในตารางนี้ นั่นคือ รหัสซึ่งมีทั้งหมด N ตัว กระจายอยู่ตามแต่ละช่องในตารางนี้

            ถึงเวลาที่จะต้องไขพาสเวิร์ดให้ได้ ตารางข้อมูลนี้มีรูปเป็นสี่เหลี่ยมจัตุรัส ขนาด 1001 x 1001 หน่วย มุมล่างซ้ายของตารางอยู่ที่ช่อง (0,0) และมุมขวาบนของตารางอยู่ที่ช่อง (1000,1000) ในระนาบ 2 มิติ คุณไม่สามารถท่องเข้าไปในตารางข้อมูลนี้ได้ เนื่องจากการระบบการป้องกันภัยขั้นสูง

            สิ่งที่คุณทำได้คือการเจาะไปยังช่องใดช่องหนึ่งในตารางตำแหน่ง (X, Y) แล้วกระจายตัวเองออกไปรอบทิศด้วยพลังงาน K คุณจะได้รหัสพาสเวิร์ดทุกตัว ที่อยู่ภายในรูปสี่เหลี่ยมจัตุรัสที่มีจุด (XK, YK) เป็นมุมล่างซ้าย และจุด (X + K, Y + K) เป็นมุมบนขวา ทั้งนี้เป็นไปได้ที่จะมีการแกะรหัสพาสเวิร์ดตัวเดิมเกิดขึ้นหลายครั้ง

            เคราะห์ร้ายที่คุณต้องเหนื่อยอีกครั้ง เมื่อพบว่าคุณสามารถเจาะตารางนี้ได้เพียง M ครั้งเท่านั้น

ครั้งนี้ สิ่งที่คุณต้องทำคือทราบให้ได้ว่า การเจาะเข้าไปยังตำแหน่งใดในตารางด้วยพลังงานเท่าไหร่ จะทำให้สามารถแกะรหัสมาได้กี่ตัว

งานของคุณ

เขียนโปรแกรมรับตำแหน่งของรหัสแต่ละตัว และตำแหน่งในการเจาะตาราง แล้วคำนวณว่า การทดลองเจาะตารางแต่ละครั้งแกะรหัสได้ทั้งสิ้นกี่ตัว

ข้อมูลนำเข้า

บรรทัดแรก ระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000) แทนจำนวนตัวของรหัส และจำนวนเต็ม M (1 M 1,000,000) แทนจำนวนครั้งของการเจาะ

อีก N บรรทัดถัดมา มีข้อมูลของรหัสทั้ง N ตัว โดยในบรรทัดที่ i + 1 ระบุจำนวนเต็ม Xi และ Yi (0 Xi, Yi 1,000) ซึ่งเป็นตำแหน่งช่องที่รหัสนั้นอยู่ในตาราง ทั้งนี้อาจมีรหัสสองตัวใดๆ อยู่ในตำแหน่งเดียวกันได้

อีก M บรรทัดต่อมา มีข้อมูลการเจาะตาราง โดยในบรรทัดที่ j + N + 1 มีจำนวนเต็ม Xj และ Yj และ Kj (0 Xj, Yj 1,000 และ 0 ≤ Kj 1,000) หมายความว่าในการเจาะตารางครั้งที่ j มีการเจาะที่ตำแหน่ง (Xj, Yj) ด้วยพลังงาน Kj เนื่องจากคุณง่วงและเบลอ เป็นไปได้ที่คุณจะเจาะตารางซ้ำที่เดิมด้วยพลังงานเดิม

ข้อมูลส่งออก

มี M บรรทัด ในบรรทัดที่ j แสดงจำนวนเต็ม Bj แทนจำนวนรหัสที่ทราบมาจากการเจาะตารางครั้งที่ j

การให้คะแนน

50% ของชุดข้อมูลทดสอบมีค่า N, M 10,000 และในทุกชุดข้อมูลทดสอบมีค่า N, M 1,000,000

 

โจทย์โดย: พศิน มนูรังษี

ที่มา: TOI.C:01-2009
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 2
0 0
0 10
10 0
10 10
5 5
5 5 5
10 10 5
5
2
5 2
0 0
2 0
1 1
3 0
6 6
2 1 2
6 6 5
4
2

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

กำลังออนไลน์: 15 ผู้เยี่ยมชมและ 1 สมาชิก (1 บอท)