F. Strange Settime limit per test4 secondsmemory limit per test32 megabytesinputstandard inputoutputstandard outputNote that the memory limit is unusual.You are given an integer n and two sequences a_1, a_2, \dots, a_n and b_1, b_2, \dots, b_n.Let's call a set of integers S such that S \subseteq \{1, 2, 3, \dots, n\} strange, if, for every element i of S, the following condition is met: for every j \in [1, i - 1], if a_j divides a_i, then j is also included in S. An empty set is always strange.The cost of the set S is \sum\limits_{i \in S} b_i. You have to calculate the maximum possible cost of a strange set.InputThe first line contains one integer n (1 \le n \le 3000).The second line contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 100).The third line contains n integers b_1, b_2, \dots, b_n (-10^5 \le b_i \le 10^5).OutputPrint one integer — the maximum cost of a strange set.ExamplesInput
9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1
Output
16
Input
2
42 42
-37 13
Output
0
Input
2
42 42
13 -37
Output
13
NoteThe strange set with the maximum cost in the first example is \{1, 2, 4, 8, 9\}.The strange set with the maximum cost in the second example is empty.
9
4 7 3 4 5 6 7 8 13
-2 3 -19 5 -6 7 -8 9 1

16 
['flows', 'math', '*2700']