Largest tile size: hints, no solution

A flooring shop cuts square tiles out of rectangular stone sheets. Sheet i measures widths[i] by heights[i] centimetres. Every tile has the same integer side length s, is cut with its edges parallel to the sheet, and cannot be assembled from off-cuts, so one sheet yields floor(width / s) times floor(height / s) whole tiles.

An order needs at least k tiles in total across all sheets. Return the largest side length s for which the sheets give at least k tiles. If the order cannot be met even with s = 1, return 0.

Side lengths can be as large as ten thousand and sheets number in the hundreds of thousands, so avoid testing every s from the top down over all the sheets.

Examples

Input

widths = [9, 6], heights = [6, 4], k = 7

Output

3

Note

Sheet 9 by 6 yields 3 by 2 tiles and sheet 6 by 4 yields 2 by 1, so 6 + 2 = 8 tiles, which is at least 7.

Input

widths = [5], heights = [5], k = 30

Output

0

Note

Sheet 5 by 5 gives 25 tiles at best, which is less than 30.

Constraints

• 1 <= widths.length = heights.length <= 400000
• 1 <= widths[i], heights[i] <= 10000
• 1 <= k <= 2000000000
• Tile counts can exceed 32 bits, so add them with wider integers

Hint 1: a nudge

If the tiles get bigger, what happens to the total number you can cut? Does it ever go up again?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing