Subset Sum Problem

You are given a list of distinct integers and a positive integer target. Your task is to determine whether there exists a subset of the given integers whose sum is exactly equal to the target.

This problem can be expressed mathematically as follows: Given a set \(S = \{a_1, a_2, \dots, a_n\}\) and a target \(T\), determine if there exists a subset \(S' \subseteq S\) such that

[ \sum_{a \in S'} a = T. ]

Please note that the input is provided via stdin and the output should be printed to stdout as either True if such a subset exists, or False otherwise. You are expected to design an efficient algorithm, for example using dynamic programming.

inputFormat

The input consists of two lines:

• The first line contains two integers, n and target, separated by a space, where n is the number of elements in the list.
• The second line contains n space-separated integers representing the elements of the list.

Constraints:

• \(1 \leq n \leq 10^4\)
• Each integer in the list is distinct.
• target is a positive integer.

outputFormat

Print True if there exists a subset of the given list that sums to target, otherwise print False.

## sample

5 9
1 2 3 4 5

True