Frog
Национална Олимпиада по Информатика 2011, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
След като принцът я целуна, Ели се превърна в жаба. Да, и за нея това беше неочаквано. Нещо повече, когато тя му проговори и му каза да я целуне още веднъж за да стане обратно човек, принцът отвърна: „Красиви момичета бол, но говореща жаба – това е яко!”.

В момента момичето се намира върху най-лявата от N водни лилии, разположени в права линия, и, както в много други задачи, иска да стигне най-дясната от тях. При това, за да минимизира пътя си, тя решава да се движи само надясно.

Както в реалния живот, тя веднага реши да си намери цел. И тъй като жабите не разполагат с нещо аналогично на пари, тя дефинира „Жабешко Удоволствие”, или ЖУ. Тя оценява всяко нещо с ЖУ и гледа да постигне възможно най-много от него. Например, тя харесва някои от лилиите (на тях има вкусни мушички) и казва, че те й носят положително ЖУ. От друга страна, други лилии са на слънце и карат кожата й да изсъхва, като това й носи отрицателно ЖУ. Ели е изчислила жабешкото удоволствие за всички лилии, като тази с индекс i има ЖУ равно на Ai.

Скачането от лилия на лилия я изморява и също влияе на нейното ЖУ (с отрицателни точки). На всичкото отгоре някои водни лилии са по-нестабилни от други и не всеки скок отнема еднакво ЖУ. Като цяло тя дефинира пет вида лилии, като скачането от лилия с индекс i на тази с индекс j отнема (j – i) * Ti, където Ti е типът на лилия i (число от 1 до 5). Забележете, че тъй като тя се движи само надясно, то j > i.

Ели още не се е научила да скача много добре, затова дължината на скоците й са ограничени. От лилия с индекс i тя може да скочи най-много Di лилии надясно, тоест до всяка лилия с индекс k, за която i < ki + Di. Помогнете на момичето, като изчислите максималното ЖУ, което може да получи при преминаването си от най-лявата до най-дясната водна лилия.
Вход
На първия ред на стандартния вход ще бъде зададен броят на водните лилии N. На следващите N реда ще има по три цели числа – Ai, Ti и Di, указващи съответно ЖУ-то за дадената лилия, нейния тип и максималното разстояние, което може да бъде скочено от нея.
Изход
На стандартния изход изведете едно единствено цяло число – максималното жабешко удоволствие, което Ели може да постигне.
Ограничения
  • 1 ≤ N ≤ 100,000
  • -10,000 ≤ Ai ≤ 10,000
  • 1 ≤ Ti ≤ 5
  • 1 ≤ Di ≤ 100,000
Примерен Вход Примерен Изход
7 -3 1 3 -5 2 8 16 5 4 15 2 9 6 5 15 -8 3 1 27 4 2 42
Един от оптималните пътища е да се скочи от първата водна лилия на третата, от нея на четвъртата и от нея на последната. Сумата на ЖУ-тата от самите лилии е -3 + 16 + 15 + 27 = 55. Изхабеното ЖУ за скоците е 2 * 1 + 1 * 5 + 3 * 2 = 13. Крайният резултат е 55 – 13 = 42.
Мрън!