Cover Them All

Problem Statement

Cover Them All Problem Description You are standing at position 0 on an infinite number line whose positions are the integers. You are given n available move distances. Move distance i has a price cost[i] . You may buy any subset of the move distances you like. Buying move distance i costs cost[i] , and it is paid exactly once: after it is bought you may move from your current position x to x + distance[i] or to x - distance[i] as many times as you wish, in any order, at no further charge. Buy the cheapest set of move distances that lets you reach every integer position on the number line. Report the total price of that set, or report -1 when no set of the offered move distances can reach every integer position. Input Format The first line contains an integer n , the number of elements in distance[] . Each of the next n lines contains one integer, distance[i] . The next line contains an integer, the number of elements in cost[] . It is equal to n . Each of the next n lines contains one