Under construction

Still being built. Things may change

Jedi versus Sith

Interview

Time limit2sMemory limit1024 MB

Summary
Given Jedi and Sith abilities that grow linearly each day, find the first day when every Jedi ability is at least the matching Sith ability, or report that it never happens.
Level

Easy3 of 10

Topics
Math, Brute force
Solved
No attempts yet

Problem

The dark side clouds everything. Impossible to see the future is.

Master Yoda

A Jedi and a Sith are stranded on an abandoned planet. Each of them knows the same number of Force abilities. Day and night, the Jedi and the Sith fight. Over time, each of them improves their abilities. Master Yoda watches the battle from the side. He knows the moment when the Jedi will become no worse than the Sith, the closest such moment. Can you sense the disturbance in the Force and answer this question?

Each Force ability is an integer. Both warriors have nn abilities. At the start, the Jedi's abilities are jij_i and the Sith's abilities are sis_i (1≤i≤n1 \le i \le n).

During the battle, the Jedi and the Sith improve their abilities. The Jedi's ii-th ability grows by lil_i each day of battle. The Sith's ii-th ability grows by did_i each day.

One fighter is no worse than the other if every one of their abilities is at least as large as the corresponding ability of the opponent.

Write a program that finds the first day when the Jedi is no worse than the Sith. Days are numbered starting from zero.

Input

The first line contains one integer nn (1≤n≤1001 \le n \le 100), the number of abilities available to the Jedi and the Sith. The second line contains nn integers jij_i, the Jedi's initial abilities. The third line contains nn integers lil_i, the Jedi's daily growth for each ability. The fourth line contains nn integers sis_i, the Sith's initial abilities. The fifth line contains nn integers did_i, the Sith's daily growth for each ability. All numbers in the input are non-negative and do not exceed 10001000.

Output

Print one integer, the number of the first day when the Jedi is no worse than the Sith. If such a day never comes, print Strong is dark side of the force.

Examples2

  1. Example 1

    Input
    2
    0 0
    2 1
    2 3
    1 0
    
    Expected output
    3
    
  2. Example 2

    Input
    2
    0 0
    2 1
    2 3
    1 1
    
    Expected output
    Strong is dark side of the force.