{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv align\u003d\"left\"\u003eYou are to solve some problem of integer linear programming. It is posed in the following way. Let x[i] be a variable which is required to be a non-negative integer (for any i from [1..N]). The goal is to minimize the function f(x[1], x[2],..., x[N])\u003dx[1]+x[2]+...+x[N] (objective function) satisfying the constraint c[1]*x[1]+c[2]*x[2]+...+c[N]*x[N]\u003dV. \u003cbr\u003eThe point X\u003d(x[1], x[2],..., x[N]) that satisfies the constraint is called \"feasible\". All feasible points form a feasible set. \u003cbr\u003eTo make things clear, let us consider the following example N\u003d2, c[1]\u003d2, c[2]\u003d4, V\u003d6. There are only two feasible points: (1, 1) and (3, 0). \u003cbr\u003eClearly, the point (1, 1) is the optimal solution, because f(1, 1)\u0026lt;f(3, 0). \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eThe first line of input contains a single positive integer N (0\u0026lt;N\u0026lt;\u003d3). The second line contains N positive integers c[i] separated by whitespaces (0\u0026lt;c[i]\u0026lt;\u003d10^6). The last line contains positive integer V (0\u0026lt;V\u0026lt;\u003d10^6). \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eOn the first line of the output file print the minimal possible value of the function f, or \"-1\" (without quotes) if the problem has no solution. \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eSample test(s)\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eInput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTest #1 \u003cbr\u003e2 \u003cbr\u003e2 4 \u003cbr\u003e6 \u003cbr\u003e \u003cbr\u003eTest #2 \u003cbr\u003e2 \u003cbr\u003e7 4 \u003cbr\u003e9 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003eOutput\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cfont face\u003d\"Courier New\"\u003e\u003c/font\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cpre\u003e\u003c/pre\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eTest #1 \u003cbr\u003e2 \u003cbr\u003e \u003cbr\u003eTest #2 \u003cbr\u003e-1 \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"left\"\u003e\u003cbr\u003e\u003cb\u003eNote\u003c/b\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003eSee picture: \u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/1c2aa65c1d0b934d01ea04cdf702f794?v\u003d1715713555\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003cdiv align\u003d\"right\"\u003e \u003c/div\u003e\u003c/div\u003e\u003cdiv align\u003d\"left\"\u003e\u003chr\u003e\u003c/div\u003e\u003ctable align\u003d\"left\" cellspacing\u003d\"7\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd\u003eAuthor:\u003c/td\u003e\u003ctd\u003eDmitry Filippov (DEF) \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eResource:\u003c/td\u003e\u003ctd\u003ePetrozavodsk Summer Training Sessions 2004 \u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003eDate:\u003c/td\u003e\u003ctd\u003eAugust 25, 2004 \u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e \u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e\r\n\u003c/div\u003e"}}]}