{"problem":{"name":"Medals","description":{"content":"You run a shop employing $N$ employees. Each employee comes to work in a fixed cycle. More specifically, starting today, the $i$\\-th employee repeats the following: working for $A_i$ consecutive days ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc106_e"},"statements":[{"statement_type":"Markdown","content":"You run a shop employing $N$ employees. Each employee comes to work in a fixed cycle. More specifically, starting today, the $i$\\-th employee repeats the following: working for $A_i$ consecutive days and then taking $A_i$ consecutive days off.\nEvery day starting today, you will come to work and give a medal to an employee of your choice who comes to work that day. (If no employee comes to work, you will do nothing that day.)\nAt least how many days does it takes to give every employee $K$ or more medals?\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\le N \\le 18$\n*   $1 \\le K \\le 10^5$\n*   $1 \\le A_i \\le 10^5$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc106_e","tags":[],"sample_group":[["3 3\n1 2 3","10\n\nFor example, you can choose to give them medals as follows:\n\n*   Give a medal to the $1$\\-st employee on the $1$\\-st, $5$\\-th, and $9$\\-th days.\n*   Give a medal to the $2$\\-nd employee on the $2$\\-nd, $6$\\-th, and $10$\\-th days.\n*   Give a medal to the $3$\\-rd employee on the $3$\\-rd, $7$\\-th, and $8$\\-th days.\n\nSince no employee comes to work on the $4$\\-th day, this is one of the ways to achieve the objective in the minimum number of days."],["10 10\n1 1 1 1 1 1 1 1 1 1","199"],["2 5\n1234 5678","10"]],"created_at":"2026-03-03 11:01:13"}}