Problem 1:

You are given a weighted directed graph with N nodes and M edges. Determine whether there exists a path from node 1 to node N such that the sum of the weights on that path is a prime number. If such a path exists, print the minimum achievable prime sum.

Constraints:

N <= 2 * 10^5 M <= 2 * 10^5 Maximum edge weight <= 2 * 10^7

Problem 2:

You are given an array a of N integers and an integer T. You need to choose a subset of numbers from a such that the LCM of the chosen numbers is less than or equal to T.

Print the maximum possible size of such a subset.

Constraints:

N <= 2 * 10^5 T <= 10^9 a[i] <= 60