1138 : หนังสือเวทมนตร์ (magicbook)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
คุณได้งานใหม่เป็นผู้ดูแลหนังสือเวทมนตร์ต้องห้ามของปีศาจ หน้าที่ของคุณคือการเดินทางไปเก็บรวบรวมหนังสือเวทมนตร์จากที่ต่างๆ บนโลก โลกที่คุณอยู่เป็นโลก 1 มิติ ซึ่งจะระบุตำแหน่งด้วยพิกัดบนเส้นจำนวน

คุณทราบว่า มีหนังสือเวทมนตร์อยู่ทั้งหมด N เล่ม โดยในทุกๆ วัน จะมีหนังสือ 1 เล่มปรากฏขึ้น ณ ที่ใดที่หนึ่งบนโลก และจะปรากฏอยู่เพียงวันเดียวเท่านั้น ก่อนจะสลายหายไป 
คุณสามารถเดินทางได้เป็นระยะทางครั้งละไม่เกิน K หน่วย ดังนั้น หากจุดที่หนังสือปรากฏขึ้นอยู่ห่างจากจุดที่คุณอยู่ไม่เกิน K หน่วย คุณจะสามารถเดินทางไปเก็บหนังสือเล่มนั้นได้ และจุดที่คุณเดินทางไปถึงก็จะเป็นที่อยู่ใหม่ของคุณ อย่างไรก็ตาม คุณได้รับอนุญาตให้เดินทางเพื่อไปเก็บหนังสือเพียงอย่างเดียว ดังนั้น จุดหมายปลายทางของการเดินทางทุกครั้งจะต้องเป็นจุดที่มีหนังสือปรากฏอยู่เท่านั้น

หนังสือเวทมนตร์แต่ละเล่มจะมีมูลค่าแตกต่างกันไป คุณต้องการเก็บหนังสือให้ได้มูลค่ารวมมากที่สุดเท่าที่จะทำได้

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

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N, K และ S (1 ≤ N ≤ 100,000; 1 ≤ K,S ≤ 1,000,000,000) แทนจำนวนหนังสือเวทมนตร์ ระยะทางมากที่สุดที่คุณสามารถเดินทางได้ และพิกัดตอนเริ่มต้นของคุณ ตามลำดับ

อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) ระบุจำนวนเต็ม Xi และ Ai (
1 ≤ Xi ≤ 1,000,000,000; 1 ≤ Ai ≤ 10,000) แทนตำแหน่งและมูลค่าของหนังสือที่ปรากฏในวันที่ i

ข้อมูลส่งออก
มีบรรทัดเดียว แทนมูลค่ารวมมากที่สุดของหนังสือที่คุณสามารถเก็บได้

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 5,000

ที่มา

โจทย์โดย: สุธี เรืองวิเศษ

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

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

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