Thog's Fortnite 2

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 5.0s
Java 15.0s
Memory limit: 64M
Java 128M

Authors:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Thog is an avid TF2 (Thog's Fortnite 2) player, and he loves unlocking achievements in TF2; it was his love for TF2 that allowed him to discover alternate dimensions, as well as interdimensional portals to travel between them (the Nobel Prize was, unfortunately, not a TF2 achievement). To his delight, every dimension contains a different TF2!

When using a portal, Thog takes W_{Y_{i}} minutes to travel from dimension X_{i} to Y_{i} (note: the reversed connection from Y_{i} to X_{i} would take W_{X_{i}} minutes). The TF2 in dimension i has A_{i} available achievements: the j^{th} achievement requires t_{j} minutes to complete and adds p_{j} points to Thog's interdimensional TF2 account.

Before Thog can start using his new technology, rival TF2 players sabotaged interdimensional travel, forcing Thog to spend at most D_{i} minutes in each dimension (which will also only allow him to gain each achievement in each dimension at most once). To make things worse, Thog's mom is coming home in H minutes, and she will force Thog to drop what he is doing and write his infamous Yahoo answer.

Help Thog find out the maximum amount of points while still starting and returning to his home (at the 0^{th} dimension) within H minutes!

(Note: DMOJ and Thog are not affiliated with Fortnite.)

Input Specification

The first line will contain H (0 \leq H \leq 10\,000) and N (1 \leq N \leq 1\,000), the maximum number of minutes Thog can spend across all dimensions and the number of dimensions (which are labelled from 0 to N - 1).

The next N lines will contain D_{i} (0 \leq D_{i} \leq 100), A_{i} (0 \leq A_{i} \leq 100), and W_{i} (0 \leq W_{i} \leq 100), the maximum number of minutes Thog can spend in the (i - 1)^{th} dimension, the number of achievements in the (i - 1)^{th} dimension, and the number of minutes it takes to travel to the (i - 1)^{th} dimension.

Before each next dimension line is printed, the next A_{i} lines directly after the i^{th} dimension will contain t_{j} (1 \leq t_{j} \leq D_{i}) and p_{j} (1 \leq p_{j} \leq 100), the number of minutes Thog needs to spend to acquire the j^{th} achievement option and the number of points received from completing the j^{th} achievement option.

The next N - 1 lines will contain X_{i} and Y_{i} (0 \leq X_{i} < Y_{i} < N), a portal that allows Thog to travel between the X_{i}^{th} dimension and the Y_{i}^{th} dimension (0-indexed).

(Important note: the connections will always form a tree from the root dimension 0.)

Constraints

For all subtasks:

1 \leq N \leq 1\,000

W_{0} = 0

Subtask 1 [20%]

N = 1

Subtask 2 [80%]

No additional constraints.

Output Specification

Output the maximum number of points Thog can achieve in H minutes (starting from his home at dimension 0).

Sample Input 1

50 1
70 4 0
20 7 
35 5
15 10
4 6

Sample Output 1

23

Explanation for Sample Output 1

The maximum number of points Thog can achieve in 50 minutes is 23: he collects 7 points in 20 minutes, 10 points in 15 minutes, and 6 points in 4 minutes (the other achievement (5 points in 35 minutes) would push him over the maximum time he can spend in his initial dimension and the time he can spend collecting points).

Sample Input 2

100 2
80 4 0
20 10
70 40
80 50
30 20
70 2 1
40 10
20 40
0 1

Sample Output 2

80

Explanation for Sample Output 2

The maximum number of points Thog can achieve in 100 minutes is 80: he collects 40 points in 70 minutes, then he goes to dimension 1 in 1 minute and collects 40 points in 20 minutes, then he returns to his initial dimension in 0 minutes (which is the guaranteed travel time to his home in all test cases).

Sample Input 3

150 3
60 3 0
50 10
30 20
10 30
100 2 5
100 20
30 50
20 1 10
20 20
0 1
0 2

Sample Output 3

120

Explanation for Sample Output 3

The maximum number of points Thog can achieve in 150 minutes is 120: he collects 20 points in 30 minutes and 30 points in 10 minutes from his initial dimension, then he goes to dimension 1 in 5 minutes and collects 50 points in 30 minutes, then he goes to the dimension 2, taking 10 minutes (0 minutes to his home and 10 minutes to the third dimension), and collects 20 points in 20 minutes, then he returns home (from the third dimension) in 0 minutes.

Sample Input 4

100 5
60 3 0
50 10
30 20
40 30
100 2 5
100 20
30 50
20 1 10
20 20
50 2 10
10 50
50 10
100 1 5
50 10
0 1
0 2
1 3
3 4

Sample Output 4

130

Explanation for Sample Output 4

The maximum number of points Thog can achieve in 100 minutes is 130: he collects 30 points in 40 minutes from his initial dimension, then he goes to dimension 1 in 5 minutes and collects 50 points in 30 minutes, then he goes to the third dimension in 10 minutes and collects 50 points in 10 minutes, then he returns home in 5 minutes (back to dimension 1, then dimension 0).


Comments

There are no comments at the moment.