The page load waterfall

simulation heap tree networks estimation

A browser loads a page. The page’s resources are numbered from 1 to n: resource 1 is the page itself, needed at moment 0. The browser learns about each other resource i from its parent resource p_i (p_i < i): a stylesheet is mentioned in the page, a font in the stylesheet, data is requested by a script. A resource becomes needed at the moment its parent is fully loaded.

The resources live on m servers; resource i on server d_i. Before requesting anything from a server, the browser opens a connection to it: finds the address, exchanges greetings, agrees on encryption. This takes c_d milliseconds. The connection to each server is opened once, at the moment some resource from that server is first needed, and after that all requests to the server go over it, any number at once. A resource that became needed before the connection is ready waits for it. A request for resource i sent at moment s finishes at moment s + t_i: t_i includes the round trip, the server’s work and the transfer.

When will the last resource be loaded? And when would it be loaded if all the connections were opened in advance, by moment 0?

Input

The first line holds n and m (1 ≤ m ≤ n ≤ 10⁵). The second holds c₁, …, c_m (0 ≤ c_d ≤ 1000). Then come n lines: p_i, d_i, t_i (p₁ = 0 and 1 ≤ p_i < i for the rest, 1 ≤ d_i ≤ m, 1 ≤ t_i ≤ 10⁵).

Output

Two numbers: the moment the last resource is loaded, and the same moment with the connections opened in advance.

Examples

Example 1

Input

8 4
120 90 150 200
0 1 60
1 1 45
1 1 70
2 3 50
1 2 80
3 1 40
1 4 30
6 2 35

Output

425 205

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 12 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

When is the connection to a server opened? When the first resource from it is needed, the first in time. Is that the same as the first by number?

2The idea

Without connections the problem is simple: a resource finishes t_i after its parent, and since the parent always has a smaller number, one pass in order of numbers is enough. The answer is the longest chain from the page to a leaf, the critical path.

With connections this will not do. Resource 3 may stand at the end of a long chain and be needed after a second, while resource 4 from the same server is needed right after the page. The connection will be opened for resource 4, but a pass in order of numbers reaches resource 3 first and opens it a second later than really happens. So the moments when resources become needed must be processed in order of time, like the events in Dijkstra’s algorithm: a heap holds “moment, resource” pairs, and the earliest is always taken out.

3Walkthrough

Put (0, 1) into the heap. Take out (τ, i): if there is no connection to server d_i yet, it starts opening now and will be ready at τ + c_d. The request goes out at max(τ, connection ready) and finishes t_i later; at that moment all of i’s children become needed: put them into the heap. The answer is the latest finish.

Why the time order is right: children become needed no earlier than their parent, so when the event τ is taken from the heap, all events before τ have been processed. So if there is no connection to the server yet, nobody asked for it before τ, and opening it at τ is right. Ties in time make no difference.

In the example the page from server 1 is ready at 180 ms: 120 go on the connection. The font from server 3 is found in the stylesheet and finishes last, at 425 ms. If all connections had been opened in advance, 205 ms would have been enough: more than half the loading time is greetings with four servers. That is why sites put the hint <link rel="preconnect"> into the page, to open the connection to the font server without waiting for the stylesheet, and keep resources on fewer servers.

3+Solution

4Complexity

Each resource enters the heap once: O(n log n). The answer without connections is O(n) in one pass.

5Common mistakes

A pass in order of numbers. Opens the connection for the server’s first resource by number, not by time: the answer comes out later than the real one. The third and fourth tests are built exactly this way.
A connection per request. It is opened once per server; resources needed after the connection is ready do not wait any more.
A recursive walk. The eighth test has a chain of 10⁵ resources: recursion in Python will hit the depth limit.
32-bit numbers. On the same chain the time reaches 10¹⁰ ms: C++ and Java need a 64-bit type.

Algorithms behind it

TEC Technique Numbers worth knowing Cache, memory, disk and network differ hundreds of times: an estimate from these numbers shows what to speed up. an estimate is a minute on a napkin 1 problem DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems