-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLemonadeChange.java
More file actions
114 lines (107 loc) · 37.6 KB
/
Copy pathLemonadeChange.java
File metadata and controls
114 lines (107 loc) · 37.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package com.leetcode.year_2020.Greedy;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.TreeMap;
/**
* https://leetcode.com/problems/lemonade-change/
*
* @author neeraj on 24/05/20
* Copyright (c) 2019, data-structures.
* All rights reserved.
*/
public class LemonadeChange {
public static void main(String[] args) {
System.out.println(lemonadeChangeWithTreeMap(new int[]{5, 5, 5, 10, 20}));
System.out.println(lemonadeChangeGreedy(new int[]{5, 5, 5, 20, 10}));
System.out.println(lemonadeChangeGreedy(new int[]{5, 5, 5, 5, 20, 10}));
System.out.println(lemonadeChangeGreedy(new int[]{5, 5, 10}));
System.out.println(lemonadeChangeGreedy(new int[]{10, 10}));
System.out.println(lemonadeChangeGreedy(new int[]{5, 5, 10, 10, 20}));
System.out.println(lemonadeChangeGreedy(new int[]{
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 20, 5, 5, 10, 5, 10, 5, 10, 5, 20, 10, 5, 5, 5, 20, 20, 5, 5, 5, 10, 5, 5, 5, 5, 20, 10, 5, 20, 5, 5, 20, 10, 20, 5, 5, 10, 10, 5, 5, 5, 10, 5, 20, 5, 5, 5, 10, 5, 20, 10, 5, 5, 5, 20, 5, 5, 5, 5, 5, 10, 5, 20, 5, 10, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 20, 10, 5, 20, 20, 5, 10, 5, 5, 5, 5, 20, 10, 10, 20, 5, 5, 5, 10, 20, 5, 5, 20, 5, 20, 20, 10, 20, 5, 10, 10, 5, 10, 10, 20, 5, 10, 10, 5, 5, 5, 5, 10, 5, 5, 5, 20, 20, 5, 5, 20, 5, 10, 5, 10, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 10, 10, 5, 5, 10, 5, 10, 20, 5, 20, 20, 5, 20, 20, 10, 5, 10, 5, 20, 20, 10, 5, 5, 5, 20, 10, 20, 20, 10, 5, 10, 20, 5, 5, 5, 20, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 20, 10, 20, 5, 20, 20, 5, 5, 5, 20, 10, 20, 10, 20, 10, 5, 10, 5, 5, 10, 10, 10, 20, 20, 5, 5, 20, 10, 5, 10, 5, 5, 5, 5, 20, 20, 5, 5, 10, 5, 10, 20, 10, 5, 5, 10, 5, 10, 5, 5, 5, 20, 20, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 10, 5, 5, 10, 5, 5, 20, 5, 5, 10, 5, 5, 20, 5, 5, 5, 20, 10, 5, 5, 10, 5, 10, 20, 5, 5, 5, 10, 20, 20, 20, 20, 5, 5, 5, 5, 20, 5, 5, 20, 5, 5, 20, 5, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 10, 10, 20, 10, 20, 5, 10, 10, 20, 5, 10, 5, 5, 5, 5, 5, 20, 20, 10, 20, 20, 5, 20, 5, 20, 5, 5, 5, 5, 20, 10, 20, 5, 5, 20, 10, 20, 5, 10, 5, 20, 5, 5, 10, 20, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 10, 20, 5, 5, 5, 5, 5, 20, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 10, 10, 5, 5, 20, 5, 10, 20, 20, 5, 5, 10, 5, 5, 5, 5, 20, 5, 20, 5, 20, 10, 5, 10, 5, 5, 10, 10, 20, 5, 5, 20, 5, 10, 20, 20, 5, 5, 5, 5, 5, 5, 20, 20, 5, 20, 10, 10, 5, 5, 5, 20, 20, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 10, 10, 20, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 10, 20, 5, 20, 5, 5, 5, 20, 5, 20, 5, 10, 20, 5, 5, 5, 10, 5, 5, 20, 5, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 10, 20, 5, 10, 10, 5, 5, 20, 20, 5, 20, 5, 20, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 10, 20, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 20, 20, 5, 5, 20, 5, 20, 5, 5, 20, 10, 20, 10, 10, 20, 10, 10, 20, 20, 10, 10, 5, 5, 20, 5, 20, 20, 5, 5, 5, 5, 10, 20, 10, 20, 5, 20, 5, 10, 20, 20, 5, 5, 20, 5, 5, 5, 20, 5, 5, 20, 5, 10, 5, 10, 10, 20, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 10, 5, 5, 5, 10, 5, 10, 10, 20, 5, 20, 20, 20, 5, 5, 5, 10, 10, 10, 20, 5, 5, 20, 20, 5, 5, 5, 10, 10, 5, 20, 5, 20, 5, 20, 5, 10, 5, 20, 5, 5, 5, 5, 20, 10, 10, 10, 5, 20, 10, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 10, 5, 5, 5, 5, 20, 5, 20, 20, 10, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 10, 5, 20, 10, 10, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 10, 10, 5, 5, 5, 5, 5, 5, 10, 10, 5, 20, 20, 5, 5, 20, 10, 10, 5, 10, 5, 5, 5, 5, 5, 5, 10, 10, 10, 20, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 5, 5, 10, 5, 10, 10, 20, 20, 5, 20, 10, 5, 10, 5, 20, 10, 5, 5, 5, 20, 5, 20, 5, 5, 20, 5, 5, 20, 20, 20, 5, 5, 10, 20, 5, 5, 10, 5, 5, 20, 10, 5, 5, 20, 5, 20, 20, 5, 20, 5, 5, 5, 10, 10, 5, 5, 20, 10, 10, 5, 5, 5, 10, 20, 5, 20, 5, 5, 20, 10, 5, 10, 20, 20, 5, 20, 10, 5, 5, 20, 20, 10, 5, 10, 5, 10, 10, 10, 5, 5, 5, 5, 5, 10, 5, 20, 10, 5, 10, 5, 20, 5, 5, 5, 20, 5, 5, 20, 10, 5, 5, 5, 20, 10, 5, 20, 5, 5, 5, 5, 10, 20, 5, 20, 5, 10, 5, 5, 5, 5, 10, 10, 20, 5, 10, 20, 20, 5, 10, 5, 20, 5, 5, 5, 5, 20, 5, 5, 20, 5, 20, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 20, 20, 20, 5, 5, 5, 5, 5, 20, 5, 5, 20, 10, 5, 5, 20, 5, 5, 10, 5, 5, 20, 20, 20, 5, 5, 5, 5, 10, 5, 5, 10, 5, 10, 5, 5, 5, 20, 5, 5, 5, 20, 5, 10, 20, 5, 10, 20, 20, 5, 20, 20, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 20, 10, 5, 20, 20, 5, 5, 5, 5, 10, 10, 5, 10, 10, 20, 10, 10, 5, 5, 20, 10, 20, 5, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 10, 5, 20, 5, 10, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 10, 20, 5, 10, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 20, 5, 5, 5, 10, 5, 20, 20, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 5, 5, 20, 10, 5, 5, 10, 10, 10, 10, 10, 10, 5, 20, 20, 10, 20, 5, 5, 20, 10, 5, 5, 20, 5, 10, 5, 5, 5, 20, 5, 5, 5, 5, 10, 10, 5, 5, 5, 20, 10, 10, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 20, 10, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 10, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 20, 10, 5, 20, 5, 5, 20, 10, 20, 5, 5, 5, 20, 20, 20, 10, 20, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 10, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 5, 5, 20, 10, 5, 20, 10, 20, 5, 10, 5, 10, 5, 5, 20, 5, 5, 10, 5, 10, 20, 5, 20, 5, 5, 5, 20, 5, 20, 5, 5, 20, 20, 20, 20, 5, 5, 10, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 5, 10, 10, 20, 5, 5, 5, 5, 5, 20, 20, 10, 10, 5, 5, 5, 5, 10, 5, 10, 10, 20, 20, 5, 10, 5, 5, 5, 10, 10, 5, 5, 10, 5, 5, 5, 10, 5, 5, 10, 5, 20, 5, 5, 5, 5, 10, 5, 10, 5, 20, 20, 5, 5, 10, 20, 10, 5, 5, 10, 10, 5, 5, 5, 20, 5, 20, 5, 20, 5, 5, 10, 10, 5, 5, 20, 5, 20, 5, 20, 10, 5, 5, 5, 5, 10, 10, 5, 20, 20, 20, 5, 10, 5, 5, 20, 5, 20, 5, 5, 20, 20, 10, 5, 5, 5, 5, 20, 10, 10, 20, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 10, 20, 10, 20, 5, 20, 10, 5, 5, 5, 20, 5, 20, 5, 5, 5, 10, 5, 20, 5, 10, 5, 5, 5, 10, 5, 10, 5, 5, 20, 5, 5, 20, 20, 20, 10, 5, 5, 20, 5, 20, 5, 10, 5, 10, 5, 5, 20, 5, 10, 5, 10, 20, 20, 5, 5, 10, 10, 5, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 20, 5, 10, 5, 5, 5, 10, 20, 5, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 10, 5, 20, 20, 10, 10, 5, 10, 10, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 20, 10, 5, 10, 5, 20, 10, 10, 5, 5, 5, 5, 10, 5, 5, 10, 10, 5, 5, 10, 5, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 5, 5, 20, 10, 5, 10, 20, 20, 10, 5, 5, 5, 5, 5, 20, 10, 10, 20, 5, 20, 5, 5, 20, 5, 5, 20, 5, 10, 10, 20, 5, 5, 20, 5, 5, 5, 10, 20, 20, 5, 20, 20, 5, 10, 20, 5, 5, 20, 20, 5, 5, 10, 5, 5, 20, 5, 5, 10, 5, 20, 20, 5, 10, 5, 5, 5, 20, 10, 5, 5, 10, 20, 5, 20, 20, 10, 10, 10, 5, 10, 5, 5, 5, 20, 5, 10, 5, 10, 10, 5, 5, 10, 20, 5, 20, 5, 5, 5, 5, 10, 10, 5, 20, 5, 5, 5, 5, 5, 5, 20, 10, 20, 20, 20, 5, 20, 10, 20, 20, 20, 5, 5, 10, 20, 10, 5, 5, 5, 10, 10, 5, 10, 20, 10, 5, 5, 5, 20, 5, 20, 5, 5, 5, 5, 5, 10, 10, 5, 20, 5, 5, 10, 5, 10, 5, 5, 20, 20, 5, 5, 20, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 20, 20, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 20, 5, 5, 10, 5, 20, 10, 5, 5, 5, 10, 10, 5, 5, 10, 5, 5, 5, 10, 5, 20, 20, 10, 5, 10, 20, 20, 5, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 20, 20, 20, 5, 10, 10, 5, 5, 5, 5, 10, 20, 5, 5, 20, 5, 20, 10, 5, 20, 10, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 10, 5, 10, 10, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 20, 20, 5, 5, 10, 5, 20, 5, 5, 20, 5, 20, 20, 5, 5, 5, 5, 20, 10, 5, 5, 5, 10, 5, 10, 5, 5, 5, 10, 10, 5, 5, 10, 10, 5, 5, 5, 5, 5, 20, 10, 20, 20, 5, 10, 5, 20, 5, 10, 5, 5, 5, 20, 20, 5, 20, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 10, 10, 5, 5, 5, 10, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 10, 5, 10, 20, 10, 5, 5, 5, 20, 20, 20, 10, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 20, 20, 20, 10, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 20, 5, 5, 10, 5, 5, 20, 5, 5, 10, 5, 20, 20, 10, 5, 20, 20, 20, 5, 10, 20, 20, 20, 20, 5, 10, 10, 5, 20, 5, 5, 5, 5, 5, 10, 5, 10, 20, 20, 5, 5, 5, 5, 5, 10, 20, 20, 5, 20, 5, 5, 5, 20, 10, 5, 5, 10, 5, 5, 10, 10, 5, 10, 20, 20, 5, 5, 10, 10, 5, 5, 5, 20, 5, 5, 5, 5, 20, 10, 10, 20, 20, 5, 20, 5, 5, 10, 10, 5, 20, 5, 5, 10, 10, 20, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 5, 10, 5, 20, 20, 20, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 20, 5, 20, 20, 10, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 10, 20, 5, 10, 20, 5, 20, 5, 5, 5, 5, 20, 5, 20, 5, 10, 5, 5, 5, 5, 5, 5, 20, 5, 10, 20, 10, 5, 10, 5, 10, 5, 5, 5, 10, 10, 5, 10, 20, 10, 5, 20, 5, 20, 5, 5, 10, 5, 20, 5, 5, 5, 10, 5, 10, 20, 5, 20, 20, 5, 5, 20, 20, 5, 10, 5, 10, 5, 20, 5, 20, 10, 5, 5, 10, 5, 20, 20, 5, 10, 5, 20, 5, 5, 5, 5, 20, 5, 5, 10, 10, 10, 5, 5, 5, 5, 5, 10, 10, 5, 20, 5, 5, 5, 5, 20, 5, 20, 5, 20, 5, 5, 5, 10, 5, 5, 10, 20, 5, 5, 10, 5, 5, 5, 10, 5, 10, 5, 5, 10, 5, 10, 5, 5, 5, 10, 20, 10, 20, 20, 5, 5, 10, 5, 5, 10, 20, 10, 20, 5, 10, 10, 20, 20, 20, 5, 10, 10, 5, 20, 5, 5, 5, 5, 5, 5, 10, 10, 5, 5, 5, 5, 10, 10, 10, 20, 5, 5, 20, 5, 5, 5, 10, 5, 20, 5, 10, 10, 10, 5, 5, 10, 20, 5, 10, 20, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 10, 5, 20, 5, 10, 10, 10, 5, 5, 5, 5, 5, 10, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 10, 10, 5, 10, 10, 5, 10, 5, 5, 5, 5, 5, 20, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 20, 10, 10, 5, 10, 5, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 20, 10, 10, 5, 10, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 20, 5, 10, 10, 20, 5, 10, 5, 20, 5, 5, 5, 5, 20, 5, 5, 20, 5, 5, 5, 10, 20, 5, 5, 10, 5, 5, 5, 5, 5, 10, 5, 20, 5, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 5, 5, 5, 5, 5, 10, 5, 10, 5, 10, 5, 20, 20, 20, 20, 20, 10, 20, 5, 10, 20, 5, 20, 20, 20, 20, 5, 20, 20, 20, 5, 5, 5, 20, 5, 5, 5, 20, 20, 5, 20, 5, 20, 10, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 10, 10, 5, 10, 10, 20, 5, 10, 5, 5, 5, 20, 10, 5, 10, 5, 20, 5, 5, 10, 5, 5, 10, 5, 20, 5, 10, 10, 5, 5, 10, 20, 5, 5, 5, 5, 5, 20, 10, 5, 10, 5, 20, 5, 20, 20, 20, 10, 5, 5, 5, 10, 10, 5, 10, 5, 5, 5, 5, 5, 20, 10, 20, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 10, 5, 20, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 20, 5, 10, 5, 5, 5, 20, 5, 20, 20, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 20, 10, 20, 5, 5, 5, 5, 10, 10, 10, 5, 10, 5, 20, 5, 10, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 20, 5, 20, 10, 5, 10, 20, 5, 10, 5, 10, 20, 5, 10, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 20, 20, 10, 5, 10, 20, 5, 20, 5, 10, 20, 20, 5, 10, 20, 5, 5, 5, 10, 20, 10, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 20, 20, 5, 5, 20, 20, 5, 10, 20, 5, 5, 5, 5, 20, 20, 10, 5, 5, 20, 5, 5, 10, 10, 5, 10, 10, 5, 20, 10, 5, 20, 5, 10, 5, 10, 5, 10, 5, 10, 5, 5, 5, 5, 5, 5, 20, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 10, 20, 10, 5, 20, 5, 10, 10, 10, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 20, 10, 5, 5, 10, 5, 10, 5, 20, 5, 5, 5, 10, 5, 5, 5, 5, 20, 5, 10, 5, 10, 20, 5, 20, 5, 5, 20, 5, 10, 5, 10, 5, 5, 5, 5, 20, 5, 10, 5, 5, 10, 5, 5, 10, 5, 10, 5, 10, 5, 5, 10, 10, 20, 5, 10, 5, 5, 5, 10, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 10, 5, 20, 20, 20, 5, 5, 5, 20, 5, 10, 10, 20, 10, 20, 5, 20, 5, 5, 20, 20, 5, 10, 10, 20, 5, 5, 5, 10, 10, 5, 10, 10, 5, 20, 20, 5, 5, 20, 20, 5, 10, 10, 10, 20, 5, 20, 5, 5, 20, 20, 5, 5, 10, 10, 5, 20, 20, 5, 5, 5, 5, 5, 20, 5, 20, 5, 10, 20, 10, 5, 20, 5, 5, 20, 5, 20, 5, 5, 5, 20, 20, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 10, 5, 5, 5, 20, 5, 20, 5, 20, 20, 20, 10, 5, 10, 5, 5, 10, 20, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 10, 10, 20, 5, 20, 5, 5, 5, 5, 5, 5, 5, 10, 10, 10, 5, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 20, 20, 10, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 10, 5, 5, 5, 20, 5, 5, 5, 10, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 5, 10, 5, 10, 5, 10, 10, 10, 5, 5, 20, 5, 10, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 10, 20, 20, 5, 20, 5, 5, 5, 10, 10, 20, 5, 20, 10, 10, 10, 10, 5, 5, 5, 5, 10, 5, 10, 10, 5, 5, 20, 10, 5, 5, 20, 20, 5, 10, 5, 5, 5, 10, 10, 5, 5, 5, 10, 10, 20, 5, 10, 20, 20, 5, 20, 20, 20, 5, 5, 20, 10, 5, 10, 10, 5, 5, 20, 5, 20, 20, 5, 5, 5, 5, 20, 5, 5, 5, 10, 5, 5, 5, 5, 5, 20, 10, 5, 10, 5, 5, 5, 5, 5, 10, 10, 5, 5, 5, 5, 10, 5, 5, 20, 5, 20, 10, 10, 5, 20, 10, 5, 10, 5, 10, 5, 20, 20, 20, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 20, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 20, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 20, 5, 5, 10, 5, 20, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 5, 20, 5, 5, 5, 5, 20, 20, 5, 5, 10, 5, 20, 5, 5, 20, 5, 20, 5, 5, 5, 10, 10, 5, 5, 5, 5, 5, 20, 5, 10, 10, 20, 20, 5, 5, 10, 5, 5, 5, 20, 10, 10, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 5, 20, 5, 10, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 10, 5, 20, 5, 20, 5, 20, 20, 10, 20, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 20, 20, 10, 5, 5, 10, 20, 5, 5, 5, 10, 20, 5, 5, 5, 20, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 10, 5, 5, 10, 5, 20, 20, 5, 5, 5, 5, 5, 5, 5, 20, 20, 20, 5, 20, 5, 10, 10, 5, 5, 20, 5, 5, 10, 5, 20, 5, 10, 5, 5, 10, 5, 20, 5, 5, 20, 10, 5, 20, 20, 5, 10, 10, 5, 20, 20, 10, 5, 20, 5, 20, 5, 5, 20, 5, 20, 10, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 10, 20, 5, 10, 10, 5, 20, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 10, 5, 5, 5, 20, 20, 10, 20, 20, 5, 10, 5, 10, 10, 20, 5, 5, 5, 10, 5, 10, 20, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 10, 5, 5, 10, 5, 20, 5, 20, 5, 10, 20, 5, 10, 5, 20, 10, 10, 10, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 10, 5, 10, 5, 10, 5, 5, 5, 5, 10, 5, 20, 20, 10, 10, 5, 20, 5, 10, 5, 10, 10, 10, 10, 5, 20, 20, 5, 10, 10, 5, 5, 20, 10, 5, 10, 5, 5, 5, 20, 5, 5, 10, 20, 5, 5, 10, 20, 5, 5, 10, 5, 5, 10, 5, 20, 10, 20, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 20, 5, 20, 5, 20, 5, 10, 5, 5, 20, 5, 5, 10, 5, 5, 5, 10, 20, 20, 20, 5, 5, 5, 5, 10, 20, 5, 5, 20, 10, 5, 5, 5, 20, 5, 5, 20, 5, 5, 10, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 10, 5, 5, 10, 10, 5, 5, 10, 5, 10, 5, 5, 5, 5, 20, 10, 5, 20, 5, 20, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 5, 20, 5, 5, 20, 10, 10, 20, 20, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 20, 20, 10, 5, 5, 20, 10, 10, 20, 5, 5, 5, 20, 10, 5, 10, 10, 5, 5, 5, 10, 5, 10, 5, 20, 5, 5, 10, 20, 10, 5, 10, 20, 5, 5, 20, 10, 5, 5, 20, 5, 20, 5, 10, 5, 20, 10, 5, 5, 10, 10, 5, 10, 5, 10, 20, 10, 5, 10, 20, 5, 5, 10, 5, 5, 10, 10, 5, 10, 10, 5, 5, 20, 5, 5, 5, 10, 5, 10, 20, 5, 20, 5, 5, 10, 5, 10, 5, 5, 20, 20, 20, 5, 5, 5, 10, 10, 5, 5, 20, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 20, 5, 20, 5, 20, 20, 5, 5, 20, 10, 20, 5, 5, 10, 5, 5, 10, 5, 5, 10, 5, 5, 20, 5, 5, 5, 20, 10, 5, 5, 10, 5, 20, 5, 5, 5, 20, 20, 20, 5, 20, 5, 5, 5, 5, 5, 20, 5, 20, 10, 5, 10, 5, 10, 5, 10, 10, 5, 20, 5, 5, 20, 10, 5, 5, 5, 20, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 10, 10, 20, 5, 5, 10, 5, 5, 5, 20, 5, 10, 20, 5, 5, 20, 5, 5, 20, 5, 10, 10, 5, 5, 20, 10, 10, 20, 5, 10, 5, 5, 10, 5, 5, 5, 20, 5, 10, 10, 20, 20, 10, 5, 5, 20, 5, 5, 10, 20, 10, 5, 5, 20, 10, 5, 10, 5, 5, 5, 10, 5, 20, 5, 5, 5, 20, 5, 20, 20, 20, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 20, 20, 5, 5, 5, 20, 5, 10, 5, 20, 5, 5, 5, 10, 10, 5, 5, 20, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 5, 5, 20, 5, 10, 10, 5, 5, 10, 20, 20, 5, 5, 5, 20, 20, 20, 20, 5, 5, 5, 10, 5, 10, 10, 5, 5, 5, 20, 5, 5, 20, 20, 10, 5, 20, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 20, 10, 10, 10, 10, 5, 10, 5, 5, 5, 10, 5, 5, 10, 10, 20, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 10, 20, 10, 20, 5, 5, 5, 5, 20, 5, 5, 5, 20, 20, 10, 20, 20, 10, 5, 5, 10, 5, 20, 5, 5, 20, 5, 5, 20, 20, 10, 5, 20, 10, 10, 10, 5, 5, 20, 5, 20, 10, 10, 10, 5, 5, 10, 5, 5, 5, 10, 5, 5, 10, 5, 10, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 10, 20, 20, 20, 5, 10, 5, 5, 10, 20, 20, 5, 20, 5, 20, 5, 5, 20, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 20, 10, 5, 10, 5, 5, 5, 20, 5, 20, 5, 10, 5, 10, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 10, 5, 5, 20, 20, 20, 5, 5, 20, 10, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 10, 10, 5, 20, 10, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 20, 5, 10, 5, 20, 5, 10, 5, 10, 20, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 20, 20, 5, 20, 5, 5, 5, 5, 5, 20, 10, 20, 5, 5, 5, 5, 20, 10, 5, 5, 10, 5, 5, 10, 5, 20, 5, 20, 5, 5, 10, 5, 5, 20, 5, 5, 10, 10, 20, 5, 5, 20, 20, 20, 5, 5, 20, 10, 5, 5, 5, 10, 5, 10, 10, 20, 5, 20, 10, 5, 20, 5, 10, 5, 5, 5, 10, 5, 20, 20, 10, 5, 5, 20, 5, 5, 5, 5, 20, 20, 10, 5, 5, 20, 5, 10, 5, 5, 10, 10, 5, 5, 5, 5, 20, 5, 10, 5, 5, 10, 10, 5, 20, 20, 5, 20, 10, 20, 20, 10, 10, 5, 10, 5, 5, 20, 20, 5, 10, 5, 5, 10, 5, 5, 10, 20, 5, 5, 5, 5, 20, 5, 5, 10, 10, 5, 10, 20, 5, 10, 5, 20, 10, 5, 10, 5, 5, 5, 5, 5, 20, 20, 5, 5, 10, 5, 5, 10, 20, 20, 10, 10, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 10, 20, 20, 10, 5, 5, 20, 20, 10, 5, 10, 20, 5, 10, 5, 5, 5, 5, 20, 5, 5, 10, 10, 5, 5, 5, 5, 10, 5, 10, 20, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 20, 5, 10, 20, 5, 10, 10, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 10, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 5, 20, 5, 20, 10, 5, 5, 5, 5, 10, 20, 5, 20, 5, 20, 5, 10, 20, 5, 10, 10, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 10, 10, 20, 5, 20, 20, 10, 5, 10, 5, 10, 10, 5, 20, 5, 5, 5, 20, 20, 10, 5, 5, 20, 20, 10, 5, 20, 10, 5, 10, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 20, 20, 10, 10, 5, 20, 20, 5, 5, 5, 10, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 10, 20, 5, 10, 5, 20, 5, 20, 5, 10, 10, 20, 5, 5, 5, 5, 10, 5, 20, 20, 5, 5, 20, 10, 20, 5, 5, 20, 5, 5, 20, 5, 20, 5, 20, 5, 10, 5, 5, 5, 5, 10, 10, 20, 5, 10, 5, 20, 20, 5, 20, 5, 10, 20, 5, 5, 5, 20, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 20, 10, 5, 20, 10, 20, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 20, 5, 10, 10, 20, 5, 20, 20, 5, 5, 5, 10, 10, 5, 5, 10, 5, 10, 5, 20, 20, 5, 5, 5, 5, 20, 10, 5, 20, 20, 10, 5, 5, 5, 10, 5, 20, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 20, 5, 20, 10, 5, 5, 20, 5, 10, 5, 5, 5, 20, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 20, 10, 10, 5, 20, 10, 5, 5, 5, 10, 10, 10, 5, 5, 20, 5, 5, 20, 5, 10, 5, 5, 20, 5, 5, 20, 5, 10, 10, 10, 5, 5, 10, 5, 10, 5, 20, 10, 20, 5, 10, 5, 10, 10, 20, 10, 10, 5, 5, 20, 5, 5, 5, 20, 10, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 20, 10, 5, 10, 5, 10, 20, 20, 5, 5, 5, 10, 20, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 20, 20, 5, 20, 5, 10, 20, 5, 10, 5, 20, 5, 20, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 10, 20, 5, 5, 20, 10, 5, 5, 20, 5, 10, 5, 10, 5, 20, 20, 5, 5, 5, 5, 5, 20, 5, 10, 20, 10, 5, 5, 20, 20, 20, 20, 5, 5, 10, 5, 20, 5, 5, 10, 20, 5, 5, 20, 5, 20, 5, 5, 20, 10, 5, 5, 5, 5, 5, 20, 10, 10, 5, 5, 5, 5, 10, 5, 20, 10, 5, 5, 5, 20, 5, 5, 20, 5, 5, 10, 5, 10, 5, 5, 5, 10, 10, 10, 20, 10, 10, 10, 5, 5, 5, 5, 10, 5, 10, 5, 5, 20, 5, 10, 10, 5, 20, 5, 20, 5, 5, 20, 20, 20, 5, 5, 5, 5, 10, 5, 20, 20, 5, 5, 5, 10, 20, 20, 5, 10, 10, 20, 10, 10, 5, 10, 5, 5, 20, 20, 20, 20, 10, 10, 5, 10, 5, 5, 5, 5, 5, 5, 10, 10, 5, 5, 10, 5, 5, 20, 5, 5, 20, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 10, 20, 20, 5, 5, 10, 5, 20, 10, 5, 5, 5, 5, 10, 5, 5, 5, 10, 10, 5, 10, 10, 20, 5, 5, 5, 5, 5, 5, 5, 20, 10, 5, 10, 5, 5, 10, 5, 20, 20, 5, 5, 5, 5, 10, 20, 5, 5, 20, 5, 20, 10, 5, 5, 10, 5, 5, 10, 5, 10, 5, 20, 5, 10, 20, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 20, 20, 5, 10, 10, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 10, 5, 20, 10, 5, 5, 20, 5, 5, 20, 5, 5, 5, 5, 20, 20, 20, 5, 10, 5, 20, 5, 5, 5, 5, 20, 10, 10, 5, 5, 5, 5, 5, 10, 10, 10, 20, 5, 5, 5, 5, 10, 20, 20, 10, 10, 5, 5, 10, 20, 10, 5, 10, 10, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 5, 5, 10, 5, 20, 10, 5, 20, 5, 20, 10, 10, 5, 5, 20, 20, 5, 5, 5, 20, 20, 5, 5, 5, 5, 20, 5, 20, 5, 10, 5, 5, 5, 5, 5, 5, 20, 10, 20, 20, 10, 5, 20, 5, 5, 10, 20, 20, 5, 5, 5, 5, 10, 10, 10, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 5, 10, 5, 20, 20, 20, 5, 10, 5, 5, 5, 5, 10, 5, 10, 5, 20, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 10, 5, 10, 10, 10, 5, 5, 5, 5, 5, 20, 10, 20, 20, 5, 5, 10, 10, 20, 10, 5, 5, 5, 5, 10, 5, 5, 20, 20, 20, 5, 20, 10, 5, 5, 5, 10, 5, 10, 5, 5, 10, 5, 5, 20, 20, 5, 5, 10, 10, 10, 20, 5, 5, 5, 5, 20, 10, 20, 5, 20, 5, 5, 10, 10, 20, 20, 10, 5, 5, 10, 20, 5, 5, 10, 5, 20, 20, 10, 5, 10, 5, 5, 5, 5, 10, 10, 5, 10, 20, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 10, 5, 5, 20, 20, 20, 20, 10, 5, 10, 20, 10, 5, 10, 5, 20, 20, 5, 5, 20, 10, 5, 20, 20, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 5, 20, 10, 20, 10, 10, 10, 5, 5, 5, 5, 5, 10, 5, 10, 20, 5, 5, 20, 10, 5, 5, 20, 10, 10, 5, 20, 5, 5, 5, 5, 10, 10, 10, 20, 5, 5, 5, 5, 20, 5, 5, 5, 10, 5, 10, 5, 5, 5, 20, 20, 20, 5, 5, 10, 5, 5, 5, 5, 20, 5, 20, 5, 20, 5, 5, 10, 20, 20, 5, 20, 20, 10, 20, 5, 5, 5, 5, 10, 5, 10, 5, 20, 20, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 10, 20, 10, 5, 10, 20, 5, 10, 20, 20, 20, 5, 20, 5, 10, 5, 20, 5, 20, 20, 20, 10, 20, 20, 5, 5, 10, 5, 10, 20, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 5, 20, 5, 10, 5, 10, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 5, 10, 5, 20, 20, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 20, 5, 20, 10, 20, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 10, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 20, 10, 5, 5, 5, 20, 5, 5, 20, 20, 5, 5, 20, 5, 20, 20, 5, 10, 5, 20, 5, 5, 20, 5, 5, 5, 10, 5, 10, 5, 20, 5, 10, 5, 20, 5, 20, 20, 10, 10, 10, 5, 5, 20, 10, 5, 20, 5, 20, 5, 5, 5, 5, 20, 5, 5, 10, 5, 10, 20, 20, 20, 5, 5, 5, 5, 5, 10, 5, 20, 5, 10, 5, 5, 20, 10, 5, 10, 10, 20, 10, 5, 5, 10, 10, 5, 5, 5, 5, 5, 10, 5, 5, 20, 10, 5, 5, 5, 20, 20, 10, 20, 5, 10, 10, 5, 5, 20, 5, 20, 5, 20, 5, 5, 5, 20, 5, 5, 5, 10, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 5, 5, 20, 20, 20, 10, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 10, 10, 5, 5, 20, 5, 5, 20, 20, 5, 5, 10, 5, 5, 5, 5, 20, 5, 5, 20, 10, 10, 10, 5, 10, 5, 10, 5, 5, 20, 20, 5, 10, 10, 5, 5, 10, 5, 10, 5, 5, 20, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 20, 5, 20, 5, 5, 5, 5, 20, 5, 5, 20, 5, 5, 20, 20, 5, 10, 5, 20, 5, 10, 5, 10, 20, 5, 5, 5, 5, 5, 20, 20, 20, 5, 5, 20, 5, 5, 20, 10, 10, 20, 10, 5, 20, 20, 5, 5, 20, 10, 5, 20, 5, 10, 10, 5, 10, 5, 5, 10, 5, 10, 5, 5, 5, 20, 5, 20, 10, 5, 20, 10, 5, 10, 20, 5, 5, 20, 10, 20, 10, 10, 20, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 20, 10, 20, 10, 5, 5, 20, 20, 5, 10, 20, 20, 5, 5, 5, 5, 5, 5, 20, 10, 20, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 20, 5, 20, 5, 5, 5, 20, 20, 5, 5, 5, 10, 20, 5, 5, 10, 20, 5, 5, 10, 20, 10, 5, 10, 5, 20, 20, 5, 10, 10, 10, 5, 5, 5, 5, 20, 10, 10, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 10, 10, 5, 5, 5, 20, 20, 10, 10, 10, 5, 5, 10, 10, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 20, 5, 5, 5, 10, 20, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 20, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 5, 10, 10, 5, 10, 10, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 20, 5, 10, 10, 10, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 10, 5, 5, 20, 20, 5, 10, 5, 20, 5, 5, 5, 10, 10, 5, 5, 20, 5, 20, 5, 10, 20, 10, 20, 5, 5, 20, 20, 5, 10, 20, 20, 5, 5, 5, 5, 20, 5, 20, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 20, 10, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 10, 10, 10, 5, 20, 5, 5, 20, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 10, 10, 5, 10, 5, 5, 5, 5, 20, 5, 20, 10, 20, 5, 10, 20, 5, 10, 5, 5, 5, 20, 20, 5, 20, 5, 5, 5, 5, 10, 20, 20, 5, 10, 5, 5, 10, 5, 20, 10, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 5, 5, 20, 5, 5, 5, 20, 20, 5, 5, 10, 5, 5, 5, 10, 5, 10, 5, 5, 5, 10, 20, 20, 5, 5, 20, 20, 20, 5, 20, 10, 10, 20, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 20, 10, 5, 5, 20, 10, 20, 20, 5, 5, 5, 10, 20, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 20, 5, 20, 20, 10, 10, 5, 10, 5, 20, 20, 5, 5, 10, 20, 10, 10, 10, 5, 5, 20, 5, 20, 5, 10, 5, 5, 5, 5, 20, 20, 5, 5, 5, 10, 5, 20, 5, 10, 10, 5, 5, 10, 10, 5, 5, 5, 20, 10, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 20, 10, 5, 10, 5, 10, 10, 5, 10, 5, 20, 5, 5, 20, 5, 5, 5, 10, 20, 5, 20, 20, 10, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 10, 5, 20, 20, 20, 10, 5, 5, 10, 5, 10, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 10, 5, 20, 5, 10, 5, 20, 5, 20, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 5, 5, 10, 10, 5, 20, 5, 5, 20, 5, 5, 10, 10, 5, 10, 5, 10, 5, 5, 5, 10, 5, 5, 10, 20, 5, 10, 5, 10, 10, 5, 5, 5, 5, 5, 10, 10, 20, 5, 20, 5, 20, 5, 10, 5, 20, 10, 20, 10, 5, 20, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 5, 10, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 10, 5, 20, 10, 20, 10, 5, 20, 5, 20, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 20, 20, 10, 20, 5, 20, 5, 5, 5, 5, 10, 5, 5, 5, 10, 20, 20, 5, 20, 5, 5, 10, 20, 10, 5, 5, 5, 5, 5, 10, 5, 10, 20, 5, 5, 5, 20, 5, 5, 5, 5, 20, 20, 5, 5, 10, 5, 5, 5, 5, 5, 20, 20, 10, 5, 20, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 10, 20, 10, 5, 20, 5, 10, 10, 5, 10, 10, 5, 5, 5, 20, 10, 5, 5, 20, 10, 5, 5, 10, 5, 5, 20, 20, 20, 10, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 5, 20, 20, 5, 10, 20, 20, 5, 10, 10, 5, 20, 20, 10, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 10, 5, 10, 10, 5, 5, 10, 5, 5, 5, 10, 5, 5, 5, 5, 20, 20, 5, 20, 20, 5, 10, 20, 10, 10, 5, 5, 20, 5, 5, 10, 5, 10, 5, 5, 10, 10, 5, 5, 5, 10, 5, 20, 5, 20, 5, 10, 5, 5, 5, 5, 10, 10, 5, 5, 20, 20, 5, 5, 5, 20, 5, 5, 20, 5, 5, 20, 5, 5, 5, 10, 10, 5, 20, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 10, 5, 10, 10, 5, 10, 5, 20, 10, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 10, 10, 10, 20, 5, 10, 5, 5, 5, 10, 5, 10, 10, 5, 20, 5, 20, 5, 5, 5, 5, 20, 10, 5, 5, 5, 20, 5, 5, 5, 10, 5, 20, 10, 20, 5, 5, 5, 5, 5, 20, 20, 5, 5, 20, 5, 10, 5, 5, 20, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 5, 5, 10, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 10, 20, 20, 10, 20, 5, 10, 5, 20, 10, 10, 5, 5, 5, 20, 20, 5, 10, 10, 5, 20, 20, 20, 20, 20, 5, 5, 20, 5, 20, 10, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 20, 5, 5, 10, 5, 5, 10, 5, 5, 5, 20, 5, 10, 20, 20, 5, 5, 5, 10, 20, 10, 5, 5, 5, 10, 5, 5, 10, 20, 10, 5, 5, 10, 5, 5, 5, 20, 5, 5, 5, 5, 5, 10, 5, 20, 5, 5, 5, 10, 10, 5, 5, 5, 5, 10, 20, 10, 10, 5, 5, 5, 5, 5, 10, 10, 5, 5, 5, 20, 10, 20, 5, 5, 10, 20, 5, 5, 5, 5, 10, 20, 20, 5, 10, 10, 20, 10, 5, 5, 5, 5, 5, 5, 10, 5, 20, 10, 5, 5, 5, 5, 10, 20, 20, 5, 20, 20, 20, 5, 5, 20, 5, 5, 10, 5, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 10, 5, 20, 20, 10, 20, 20, 10, 10, 10, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 20, 5, 5, 5, 5, 5, 10, 10, 5, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 10, 10, 10, 5, 10, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 10, 20, 5, 5, 5, 10, 20, 10, 20, 10, 5, 5, 20, 5, 5, 20, 5, 10, 20, 5, 20, 5, 5, 20, 5, 5, 5, 10, 5, 20, 10, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 20, 5, 5, 10, 20, 20, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 5, 10, 5, 20, 10, 5, 5, 20, 5, 20, 10, 5, 20, 5, 5, 5, 10, 5, 10, 10, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 20, 20, 10, 5, 20, 5, 10, 5, 10, 5, 5, 5, 10, 10, 10, 5, 5, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 5, 10, 20, 5, 5, 5, 20, 5, 5, 10, 20, 5, 20, 5, 20, 5, 10, 5, 5, 5, 10, 5, 20, 5, 5, 5, 20, 5, 10, 10, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 5, 5, 5, 10, 5, 10, 5, 20, 5, 10, 5, 5, 20, 5, 5, 10, 20, 5, 10, 5, 20, 5, 10, 20, 10, 5, 10, 10, 5, 5, 5, 20, 5, 5, 20, 5, 10, 20, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 20, 5, 20, 10, 10, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 20, 10, 5, 20, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 10, 5, 20, 10, 20, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 10, 5, 20, 10, 5, 10, 20, 20, 10, 5, 20, 10, 5, 10, 20, 5, 5, 10, 5, 5, 20, 10, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 20, 10, 5, 5, 5, 20, 5, 10, 10, 5, 10, 5, 20, 5, 20, 5, 5, 5, 5, 20, 5, 10, 20, 5, 5, 10, 5, 20, 5, 5, 10, 5, 10, 10, 20, 5, 5, 10, 10, 10, 20, 5, 5, 10, 5, 5, 10, 5, 10, 20, 10, 5, 10, 5, 20, 10, 20, 20, 5, 20, 5, 10, 5, 5, 20, 5, 20, 5, 20, 5, 20, 10, 5, 10, 5, 10, 5, 5, 5, 5, 20, 5, 5, 5, 10, 20, 5, 10, 10, 20, 20, 5, 5, 5, 10, 5, 5, 20, 5, 5, 5, 10, 5, 10, 5, 5, 10, 10, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 20, 20, 5, 20, 5, 20, 5, 5, 5, 5, 10, 10, 20, 5, 20, 10, 5, 20, 20, 5, 20, 5, 5, 5, 20, 5, 5, 10, 5, 10, 10, 5, 10, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 5, 20, 20, 10, 5, 5, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 5, 20, 10, 5, 20, 5, 5, 5, 10, 10, 5, 5, 10, 5, 20, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 20, 5, 5, 20, 5, 20, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 20, 20, 5, 5, 20, 5, 5, 20, 5, 5, 20, 5, 5, 10, 5, 5, 10, 5, 5, 20, 5, 10, 5, 5, 20, 5, 10, 5, 20, 20, 5, 10, 5, 20, 5, 5, 5, 5, 20, 10, 20, 10, 5, 20, 5, 5, 10, 5, 5, 5, 10, 20, 20, 5, 5, 5, 5, 5, 10, 5, 10, 5, 20, 5, 5, 5, 10, 20, 10, 5, 20, 5, 5, 5, 5, 5, 20, 5, 10, 20, 5, 5, 20, 5, 5, 10, 10, 5, 5, 5, 20, 20, 10, 10, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 20, 10, 20, 20, 20, 10, 5, 5, 5, 5, 10, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 20, 10, 5, 5, 10, 20, 10, 10, 5, 5, 10, 5, 10, 20, 20, 5, 5, 5, 20, 5, 5, 10, 20, 10, 10, 5, 5, 10, 10, 5, 5, 20, 5, 5, 5, 20, 20, 10, 10, 20, 5, 5, 5, 10, 10, 20, 10, 5, 20, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 20, 5, 20, 5, 5, 10, 5, 5, 20, 10, 10, 20, 20, 5, 5, 20, 10, 10, 5, 10, 5, 20, 5, 10, 5, 5, 5, 5, 10, 10, 5, 5, 5, 20, 10, 5, 5, 10, 5, 10, 5, 10, 10, 5, 5, 20, 10, 5, 5, 5, 5, 10, 5, 10, 5, 10, 5, 5, 20, 5, 10, 5, 5, 5, 20, 5, 10, 5, 10, 5, 20, 10, 5, 5, 10, 5, 5, 5, 5, 5, 20, 10, 10, 20, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 10, 5, 5, 10, 5, 10, 20, 5, 5, 20, 5, 5, 5, 5, 10, 20, 10, 5, 5, 20, 20, 5, 5, 5, 20, 20, 5, 5, 20, 10, 5, 20, 5, 20, 5, 5, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 10, 20, 10, 10, 5, 10, 5, 5, 5, 5, 20, 5, 5, 10, 20, 5, 10, 5, 20, 10, 20, 5, 20, 5, 10, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 10, 5, 5, 10, 10, 20, 5, 5, 5, 10, 5, 10, 5, 5, 10, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 20, 5, 20, 5, 5, 10, 5, 10, 5, 5, 10, 5, 5, 5, 20, 5, 20, 20, 10, 10, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 20, 5, 5, 5, 10, 10, 10, 5, 5, 20, 10, 5, 20, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 10, 10, 10, 20, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 10, 5, 5, 20, 20, 5, 5, 20, 20, 5, 5, 5, 20, 10, 10, 10, 5, 20, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 10, 5, 5, 10, 5, 10, 10, 5, 5, 5, 5, 5, 5, 10, 5, 10, 20, 10, 5, 5, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 20, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 20, 20, 5, 5, 5, 20, 5, 5, 10, 5, 10, 10, 20, 20, 5, 20, 5, 5, 5, 20, 10, 5, 5, 10, 5, 5, 10, 5, 5, 20, 5, 5, 5, 5, 5, 5, 10, 5, 10, 20, 5, 5, 5, 5, 10, 5, 10, 20, 5, 10, 5, 10, 5, 5, 20, 5, 5, 20, 5, 20, 5, 5, 5, 5, 20, 5, 10, 5, 5, 5, 5, 5, 20, 5, 5, 10, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 20, 5, 10, 20, 10, 5, 5, 5, 5, 20, 10, 5, 20, 5, 5, 5, 20, 5, 5, 20, 10, 5, 5, 5, 5, 20, 5, 20, 10, 5, 5, 20, 20, 10, 5, 10, 10, 5, 10, 5, 5, 5, 5, 20, 20, 10, 5, 5, 5, 10, 5, 20, 10, 5, 5, 5, 20, 10, 10, 5, 5, 5, 10, 5, 20, 5, 5, 5, 5, 10, 5, 5, 10, 10, 10, 20, 20, 5, 20, 5, 20, 5, 5, 5, 5, 20, 5, 20, 5, 5, 5, 10, 5, 5, 5, 20, 5, 5, 5, 5, 5, 20, 20, 10, 10, 20, 5, 5, 5, 20, 10, 5, 5, 5, 20, 5, 20, 5, 5, 5, 10, 20, 20, 10, 5, 5, 5, 20, 5, 20, 5, 10, 10, 5, 20, 5, 20, 5, 10, 5, 10, 20, 5, 20, 10, 20, 5, 20, 20, 5, 5, 5, 5, 20, 5, 5, 5, 10, 5, 10, 10, 5, 10, 20, 20, 5, 5, 20, 10, 5, 5, 5, 5, 20, 10, 5, 10, 5, 5, 5, 5, 5, 10, 5, 10, 5, 5, 5, 5, 5, 10, 5, 20, 5, 10, 5, 20, 5, 5, 5, 20, 10, 20, 10, 20, 20, 5, 20, 5, 10, 5, 20, 20, 20, 5, 20, 5, 5, 10, 5, 10, 10, 10, 10, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 5, 5, 5, 20, 5, 20, 10, 10, 5, 10, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 20, 5, 10, 10, 20, 5, 20, 5, 20, 5, 5, 5, 10, 5, 5, 5, 20, 10, 20, 10, 5, 5, 20, 10, 5, 5, 5, 5, 10, 5, 20, 20, 5, 20, 20, 5, 10, 5, 5, 5, 5, 5, 10, 10, 20, 20, 10, 5, 10, 5, 20, 10, 10, 5, 10, 5, 5, 20, 5, 20, 10, 10, 5, 10, 20, 20, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 10, 5, 5, 5, 10, 5, 20, 5, 5, 10, 20, 5, 5, 20, 10, 10, 5, 20, 5, 20, 20, 10, 5, 5, 20, 5, 5, 5, 10, 20, 5, 5, 5, 5, 20, 10, 5, 20, 5, 20, 5, 20, 5, 5, 10, 5, 10, 20, 10, 5, 10, 5, 5, 5, 5, 10, 10, 20, 5, 5, 10, 5, 10, 5, 5, 10, 5, 20, 5, 20, 5, 5, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 20, 5, 5, 10, 20, 20, 5, 20, 10, 5, 20, 20, 5, 20, 20, 10, 5, 5, 5, 20, 5, 5, 20, 5, 10, 5, 20, 10, 10, 10, 5, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 20, 5, 5, 10, 5, 10, 5, 5, 20, 5, 20, 20, 5, 10, 5, 5, 10, 10, 5, 5, 5, 10, 5, 5, 10, 20, 5, 10, 5, 5, 10, 20, 10, 20, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 5, 5, 5, 5, 5, 10, 5, 5, 20, 5, 5, 10, 5, 5, 20, 20, 10, 5, 5, 5, 5, 5, 5, 5, 5, 20, 20, 5, 5, 5, 10, 5, 5, 10, 5, 5, 20, 5, 20, 20, 5, 5, 10, 5, 20, 5, 5, 5, 20, 5, 20, 10, 5, 5, 5, 5, 5, 5, 10, 20, 5, 5, 5, 20, 5, 20, 20, 5, 5, 20, 10, 10, 5, 20, 5, 5, 20, 20, 5, 10, 5, 5, 5, 5, 5, 20, 10, 5, 5, 5, 5, 5, 5, 10, 10, 5, 5, 20, 5, 5, 5, 10, 5, 10, 20, 5, 20, 10, 20, 5, 20, 5, 20, 5, 10, 10, 10, 5, 20, 5, 5, 10, 10, 5, 5, 10, 20, 20, 5, 5, 5, 5, 5, 5, 20, 5, 5, 20, 20, 10, 5, 5, 20, 5, 5, 5, 5, 10, 10, 5, 5, 20, 5, 5, 5, 5, 10, 10, 5, 5, 5, 10, 20, 10, 20, 5, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 20, 20, 10, 10, 5, 20, 5, 20, 5, 10, 5, 5, 5, 20, 5, 5, 10, 10, 5, 10, 20, 5, 5, 20, 5, 10, 5, 5, 5, 5, 20, 5, 20, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 10, 5, 20, 5, 20, 5, 10, 5, 10, 5, 5, 5, 5, 5, 20, 10, 5, 10, 10, 10, 20, 10, 5, 5, 20, 5, 5, 20, 5, 5, 20, 10, 20, 20, 20, 5, 10, 10, 5, 20, 5, 5, 5, 5, 20, 5, 20, 5, 5, 10, 20, 5, 5, 5, 5, 10, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 20, 20, 5, 20, 5, 5, 5, 5, 20, 5, 5, 5, 5, 5, 20, 5, 10, 5, 5, 10, 5, 5, 5, 5, 20, 20, 5, 20, 5, 5, 5, 20, 20, 20, 20, 5, 5, 10, 20, 5, 5, 5, 20, 5, 5, 20, 20, 5, 10, 5, 5, 20, 10, 5, 10, 5, 10, 10, 20, 10, 5, 5, 20, 20, 5, 5, 5, 10, 5, 20, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 20, 5, 5, 5, 5, 10, 5, 5, 20, 10, 10, 10, 20, 5, 5, 20, 5, 20, 5, 5, 5, 10
}));
}
public static boolean lemonadeChangeWithTreeMap(int[] change) {
TreeMap<Integer, Integer> changeWithFrequency = new TreeMap<>();
for (int customerPaid : change) {
changeWithFrequency.put(customerPaid, changeWithFrequency.getOrDefault(customerPaid, 0) + 1);
int changeToBeReturned = customerPaid - 5; // Since it's 5$ lemonade
while (changeToBeReturned > 0) {
Map.Entry<Integer, Integer> floorEntry = changeWithFrequency.floorEntry(changeToBeReturned);
if (floorEntry == null) {
return false; // Not possible at all
}
changeToBeReturned -= floorEntry.getKey();
if (floorEntry.getValue() == 1) {
changeWithFrequency.remove(floorEntry.getKey());
} else {
changeWithFrequency.put(floorEntry.getKey(), floorEntry.getValue() - 1); // Reducing the change, since we already gave to customer
}
}
}
return true;
}
/**
* This is the right approach.... to clear with the highest change as possible... but due to time constraint it is giving
* TLE for the last input in the test case.
* <p>
* So let's think of a Greedy approach.
* but we need to consider few things.... we can never return 20 as change...since the max coin in this shop is
* of 20 and you have to pay 5$ for lemonade..
* So now we are left with 10 and 5.... coins now we know in this scenario how important lower demoninations coins are.
* As a shop owner i would want to get rid of 10 instead of 5 as 5 coins give me more flexibility.
* <p>
* So let's look for the solution lemonadeChangeGreedy for different approach.
*
* @param bills
* @return
*/
public static boolean lemonadeChange(int[] bills) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((A, B) -> B - A);
Stack<Integer> stack = new Stack<>();
for (int bill : bills) {
stack = new Stack<>();
if (bill - 5 > 0) {
if (maxHeap.isEmpty()) return false; // We don't have change to give.
int diff = bill - 5;
while (diff > 0) {
if (maxHeap.isEmpty()) return false;
int top = maxHeap.poll();
if (top <= diff) {
diff -= top;
} else {
stack.push(top);
}
}
if (diff == 0) {
while (!stack.isEmpty()) {
maxHeap.add(stack.pop());
}
}
}
maxHeap.add(bill);
}
return true;
}
public static boolean lemonadeChangeGreedy(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) { // We got a 5 dollar
five++;
} else if (bill == 10) { // We got a 10 dollar
five--;
ten++;
} else { // We got a 20 dollar
if (ten > 0) {
five--;
ten--;
} else {
five -= 3; // We have to give three 5 dollar as change.
}
}
if (five < 0) return false;
}
return true;
}
}