C. Bamboo Partition

Codeforces

IDCF823C

Time2000ms

Memory512MB

Difficulty—

data structuresimplementationmathtwo pointers

Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are _n_ bamboos in a row, and the _i_\-th from the left is _a__i_ meters high. Vladimir has just planted _n_ bamboos in a row, each of which has height 0 meters right now, but they grow 1 meter each day. In order to make the partition nice Vladimir can cut each bamboo once at any height (no greater that the height of the bamboo), and then the bamboo will stop growing. Vladimir wants to check the bamboos each _d_ days (i.e. _d_ days after he planted, then after 2_d_ days and so on), and cut the bamboos that reached the required height. Vladimir wants the total length of bamboo parts he will cut off to be no greater than _k_ meters. What is the maximum value _d_ he can choose so that he can achieve what he wants without cutting off more than _k_ meters of bamboo? ## Input The first line contains two integers _n_ and _k_ (1 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ 1011) — the number of bamboos and the maximum total length of cut parts, in meters. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the required heights of bamboos, in meters. ## Output Print a single integer — the maximum value of _d_ such that Vladimir can reach his goal. [samples] ## Note In the first example Vladimir can check bamboos each 3 days. Then he will cut the first and the second bamboos after 3 days, and the third bamboo after 6 days. The total length of cut parts is 2 + 0 + 1 = 3 meters.

Samples

Input #1

3 4
1 3 5

Output #1

Input #2

3 40
10 30 50

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Bamboo Partition",
    "description": {
      "content": "Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF823C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are _...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments