Path Sum

Problem statement

A game map gives each station a signed energy adjustment. A player starts at the root and must finish at a leaf. The designer wants to know whether some complete route produces a specified total energy adjustment. Your task Determine whether there is a root-to-leaf path whose node values sum exactly to target. Include both the root and leaf in the sum. Important details A route cannot stop early at an internal node even if its partial sum matches. Negative values are allowed, so a partial total above target cannot safely be pruned. The empty tree has no root-to-leaf path. Worked example With root 5 and leaf children 3 and 8, the possible complete totals are 8 and 13. Target 8 is reachable through the left child, so print true.

Input format

The first line contains target, followed by the tree description. The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print true if the condition holds, otherwise false.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children. -1000000000 <= target <= 1000000000.

Sample input

8
3
5 1 2
3 -1 -1
8 -1 -1

Sample output

true