Problem Description
Salmons are common in Japanese Restaurants. They can be served in a variety of ways: sashimi, sushi, steamed, salad.. etc
Rar the Cat is currently sitting in a Japanese Restaurant writing this problem statement. He has noticed that there is salmon in almost every single dish on the menu. However, upon scrutinization, he has found that this is because some dishes contain some other dishes. For example, a Premium Bento (Japanese Rice Set) contains Salmon Maki (Salmon Sushi).
The Premium Bento is priced at a higher price than the salmon maki and making it requires six salmon maki and five slices of salmon sashimi. On the other hand, one salmon maki requires two slices of salmon sashimi to make.
In view of the upcoming Chinese New Year, the Japanese Restaurant has also launched a Yu Sheng (Teochew Raw Fish Salad) dish that requires one hundred and seventy nine slices of salmon sashimi to create. One of this dish (Yu Sheng) is also included in a Chinese New Year Gift Box together with twenty four Japanese Bentos, sixty seven Salmon Maki and eighty eight slices of Salmon sashimi.
Rar the Cat is tempted to buy the salmon dishes but he has no money to buy from the Japanese Restaurants. Since Japanese Restaurants usually sell dishes for an expensive price, he decides to turn to a cheaper alternative -- NTUC FairPrice (Supermarket).
NTUC FairPrice sells salmon fishes as an entire fish. Being an experienced salmon fish eater, he estimates the salmon fish he plans to buy to be able to make exactly N slices of salmon sashimi. With this, he wants to know what is the maximum value of his salmon fish if he were to make the above salmon dishes (in $). To do so, he has provided you with a simplified menu of the Japanese Store.
| Item |
Price per Item ($) |
| Salmon Sashimi |
2 |
| Premium Bento |
60 |
| Salmon Maki |
7 |
| Yu Sheng |
588 |
| Chinese New Year Gift Box |
2888 |
Since Rar the Cat has limited amounts of other resources (Eg. Rice), he can only make up to 1023 of each item on the list.
Input
The input contains only a single integer, N.
Output
Output a single integer, the maximum value of his salmon fish if he were to make the above salmon dishes (in $). To do so, he has provided you with a simplified menu of the Japanese Store.
Subtasks
Subtask 1 (7 marks): 0 ≤ N < 17
Subtask 2 (46 marks): 0 ≤ N ≤ 2000
Subtask 3 (47 marks): 0 ≤ N ≤ 1000000
Subtask 4 (0 marks): Sample Testcases
Limit has been increased to N = 1000000
Sample Input 1
16
Sample Output 1
56
Rar the Cat can obtain the maximum value by making 8 Salmon Makis which are valued at $7 each.
Sample Input 2
1023
Sample Output 2
3643
Sample Input 3
32767
Sample Output 2
116956