497. Minimum Speed to Arrive on Time

You must travel through a sequence of train rides whose distances are given. Each ride departs only on integer hours, so for all but the last ride the time taken is rounded up to the next integer hour; the last ride is not rounded. Given the distances and the available time (provided as hour multiplied by 100 to keep it an integer), return the minimum positive integer speed needed to arrive on time, or -1 if impossible. Input: '[dist], hourScaled'.

Input: '[dist], hourScaled' (hour x100).

Output: Integer — the minimum speed, or -1.

Examples

Input: [1,3,2], 600
Output: 1
Explanation: At speed 1 total time is exactly 6 hours.

Input: [1,3,2], 195
Output: 5
Explanation: hour=1.95 needs speed 5.

Input: [1,3,2], 105
Output: -1
Explanation: hour=1.05 < 2 minimum rounded hours.

Constraints

• 1<=n<=10^5
• 1<=dist<=10^5
• hourScaled>=100

Asked by