Smallest Prime Subset Sum

Given an array of integers, your task is to find a non-empty subset of the array whose sum is a prime number. If there exists one or more such subsets, output the smallest prime number among these sums. Otherwise, output -1.

A prime number \(p\) is defined as an integer greater than 1 that has no positive divisors other than 1 and itself, i.e. \(p > 1\) and for any integer \(d\) such that \(1 < d < p\), \(d\) does not evenly divide \(p\).

Note that the subset does not need to consist of contiguous elements.

inputFormat

The first line of the input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers denoting the elements of the array.

outputFormat

Output a single integer — the smallest prime number obtainable as the sum of any non-empty subset of the array. If no subset with a prime sum exists, output -1.

5
3 5 7 -2 8

3