1138 : หนังสือเวทมนตร์ (magicbook)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
คุณได้งานใหม่เป็นผู้ดูแลหนังสือเวทมนตร์ต้องห้ามของปีศาจ หน้าที่ของคุณคือการเดินทางไปเก็บรวบรวมหนังสือเวทมนตร์จากที่ต่างๆ บนโลก โลกที่คุณอยู่เป็นโลก 1 มิติ ซึ่งจะระบุตำแหน่งด้วยพิกัดบนเส้นจำนวน
คุณทราบว่า มีหนังสือเวทมนตร์อยู่ทั้งหมด N เล่ม โดยในทุกๆ วัน จะมีหนังสือ 1 เล่มปรากฏขึ้น ณ ที่ใดที่หนึ่งบนโลก และจะปรากฏอยู่เพียงวันเดียวเท่านั้น ก่อนจะสลายหายไป คุณสามารถเดินทางได้เป็นระยะทางครั้งละไม่เกิน K หน่วย ดังนั้น หากจุดที่หนังสือปรากฏขึ้นอยู่ห่างจากจุดที่คุณอยู่ไม่เกิน K หน่วย คุณจะสามารถเดินทางไปเก็บหนังสือเล่มนั้นได้ และจุดที่คุณเดินทางไปถึงก็จะเป็นที่อยู่ใหม่ของคุณ อย่างไรก็ตาม คุณได้รับอนุญาตให้เดินทางเพื่อไปเก็บหนังสือเพียงอย่างเดียว ดังนั้น จุดหมายปลายทางของการเดินทางทุกครั้งจะต้องเป็นจุดที่มีหนังสือปรากฏอยู่เท่านั้น
คุณทราบว่า มีหนังสือเวทมนตร์อยู่ทั้งหมด 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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 31 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)