#1422. 内存对齐

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Lrefrain

题目描述

路明非有一个结构体,里面有个变量,其中第个变量的大小是个字节。

已知该结构体的起始地址是0,该结构体可以以任意顺序排列这个变量,每个变量会占用其大小个字节。

例如一个大小为的变量起始位置是,则其终止位置则为

由于一些未知原因,我们要求,也即的倍数。

这就意味着在该结构体内,相邻的两个变量之间可能会有空字节。

排列中最后一个变量的终止位置即为结构体的终止位置。

结构体的大小定义为终止位置和起始位置之间被结构体占用的字节数(空字节也算作被占用)。

现在川墨瞳想让你求出,对于这种排列,路明非的结构体的大小最小是多少。

输入格式

第一行,一个整数

第二行,个用空格隔开的整数,分别表示

输出格式

一行一个整数表示路明非的结构体大小最小是多少

样例

样例输入

2
2 3

样例输出

6

样例解释

这两个变量有两种排列方式,但是都需要占用6字节的大小。

如果按照2 3的顺序排列,大小为2的变量占据了0,1两字节,大小为3的变量因为其起始地址必须被3整除,所以占据3,4,5三个字节。总共占据了6字节大小。

如果按照3 2的顺序排列,大小为3的变量占据了0,1,2两字节,大小为2的变量因为其起始地址必须被2整除,所以占据4,5两个字节。总共占据了6字节大小。

数据范围与提示